A class of graphs is -bounded if there is a function such that for all induced subgraphs of a graph in . If can be chosen to be a polynomial, we say that is polynomially -bounded. Esperet proposed a conjecture that every -bounded class of graphs is polynomially -bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are -bounded but not polynomially -bounded. Nevertheless, inspired by Esperet’s conjecture, we introduce Pollyanna classes of graphs. A class of graphs is Pollyanna if is polynomially -bounded for every -bounded class of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.

生成讲解博客的中文版本

生成AI智能校验的中文版本