Separating Polynomial $$\chi $$-Boundedness from $$\chi $$-Boundedness

Abstract

Abstract Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function $$f:\mathbb {N}\rightarrow \mathbb {N}\cup \{\infty \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:mi>N</mml:mi> <mml:mo>→</mml:mo> <mml:mi>N</mml:mi> <mml:mo>∪</mml:mo> <mml:mo>{</mml:mo> <mml:mi>∞</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> with $$f(1)=1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> and $$f(n)\geqslant \left( {\begin{array}{c}3n+1\\ 3\end{array}}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⩾</mml:mo> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mn>3</mml:mn> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow/> <mml:mn>3</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> , we construct a hereditary class of graphs $${\mathcal {G}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> such that the maximum chromatic number of a graph in $${\mathcal {G}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> with clique number n is equal to f ( n ) for every $$n\in \mathbb {N}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> . In particular, we prove that there exist hereditary classes of graphs that are $$\chi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>χ</mml:mi> </mml:math> -bounded but not polynomially $$\chi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>χ</mml:mi> </mml:math> -bounded.

Topics & Concepts