Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness

Abstract

A class $\mathcal{F}$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi (H)\le f(\omega (H))$ for all induced subgraphs $H$ of a graph in $\mathcal{F}$. If $f$ can be chosen to be a polynomial, we say that $\mathcal{F}$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class $\mathcal{C}$ of graphs is Pollyanna if $\mathcal{C}\cap \mathcal{F}$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal{F}$ of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.

arXiv comment36 pages, 12 figures; Fixed a minor mistake in the proof of Proposition 4.2, replacing $\omega -1$ with $\omega$ (thanks to Yian Xu and Kaiyang Lan)

References in corpus (8)

• Parameterized algorithm for weighted independent set problem in bull-free graphs
• Circle graphs are quadratically $\chi$-bounded
• Substitution and $\chi$-Boundedness
• Separating polynomial $\chi$-boundedness from $\chi$-boundedness
• Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors
• On-line approach to off-line coloring problems on graphs with geometric representations
• Polynomial bounds for chromatic number VI. Adding a four-vertex path
• The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring