Reuniting $\ddot{I}‡$-boundedness with polynomial $\ddot{I}‡$-boundedness

Abstract

A class $\mathcal{F}$ of graphs is $\ddot{I}‡$-bounded if there is a function $f$ such that $\ddot{I}‡(H)\le f(\ddot{I}‰(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 $\ddot{I}‡$-bounded. Esperet proposed a conjecture that every $\ddot{I}‡$-bounded class of graphs is polynomially $\ddot{I}‡$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\ddot{I}‡$-bounded but not polynomially $\ddot{I}‡$-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 $\ddot{I}‡$-bounded for every $\ddot{I}‡$-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.

36 pages, 12 figures; Fixed a minor mistake in the proof of Proposition 4.2, replacing $\ddot{I}‰-1$ with $\ddot{I}‰$ (thanks to Yian Xu and Kaiyang Lan)