论文标题
将多项式$χ$绑定与$χ$结合分开
Separating polynomial $χ$-boundedness from $χ$-boundedness
论文作者
论文摘要
从Carbonero，Hompe，Moore和Spirkl的最新论文中扩展了这个想法，对于每个功能$ f \ colon \ Mathbb {n} \至\ Mathbb {n} \ cup \ cup \ cup \ {\ infty \} $，带有$ f（1）= 1 $ and $ f（1）= 1 $ and $ f（n）图类别$ \ MATHCAL {G} $，使得$ \ Mathcal {g} $的最大色度数量$ n $等于每个$ n \ in \ Mathbb {n} $的$ f（n）$。特别是，我们证明存在的遗传类别类别是$χ$结合但不是多项式$χ$结合的。
Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function $f\colon\mathbb{N}\to\mathbb{N}\cup\{\infty\}$ with $f(1)=1$ and $f(n)\geq\binom{3n+1}{3}$, we construct a hereditary class of graphs $\mathcal{G}$ such that the maximum chromatic number of a graph in $\mathcal{G}$ with clique number $n$ is equal to $f(n)$ for every $n\in\mathbb{N}$. In particular, we prove that there exist hereditary classes of graphs that are $χ$-bounded but not polynomially $χ$-bounded.
