Separating Polynomial χ -Boundedness from χ -Boundedness
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
jats:titleAbstract</jats:title>jats:pExtending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function jats:inline-formulajats:alternativesjats:tex-math$$f:\mathbb {N}\rightarrow \mathbb {N}\cup {\infty }$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mif</mml:mi> mml:mo:</mml:mo> mml:miN</mml:mi> mml:mo→</mml:mo> mml:miN</mml:mi> mml:mo∪</mml:mo> mml:mo{</mml:mo> mml:mi∞</mml:mi> mml:mo}</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> with jats:inline-formulajats:alternativesjats:tex-math$$f(1)=1$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mif</mml:mi> mml:mo(</mml:mo> mml:mn1</mml:mn> mml:mo)</mml:mo> mml:mo=</mml:mo> mml:mn1</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and jats:inline-formulajats:alternativesjats:tex-math$$f(n)\geqslant \left( {\begin{array}{c}3n+1\ 3\end{array}}\right) $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mif</mml:mi> mml:mrow mml:mo(</mml:mo> mml:min</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:mn3</mml:mn> mml:min</mml:mi> mml:mo+</mml:mo> mml:mn1</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> mml:mtr mml:mtd mml:mrow <mml:mrow /> mml:mn3</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, we construct a hereditary class of graphs jats:inline-formulajats:alternativesjats:tex-math$${\mathcal {G}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miG</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> such that the maximum chromatic number of a graph in jats:inline-formulajats:alternativesjats:tex-math$${\mathcal {G}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miG</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> with clique number jats:italicn</jats:italic> is equal to jats:italicf</jats:italic>(jats:italicn</jats:italic>) for every jats:inline-formulajats:alternativesjats:tex-math$$n\in \mathbb {N}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:min</mml:mi> mml:mo∈</mml:mo> mml:miN</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>. In particular, we prove that there exist hereditary classes of graphs that are jats:inline-formulajats:alternativesjats:tex-math$$\chi $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miχ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-bounded but not polynomially jats:inline-formulajats:alternativesjats:tex-math$$\chi $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miχ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-bounded.</jats:p>
Description
Keywords
Journal Title
Conference Name
Journal ISSN
1439-6912