Polynomial bounds for chromatic number II: Excluding a star‐forest
Polynomial bounds for chromatic number II: Excluding a star‐forest
复制标题
色数 II 的多项式界限：排除星形森林
DOI：
10.1002/jgt.22829
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
Gyárfás-Sumner 猜想指出，对于每个森林 H $H$，存在一个函数 f H ${f}_{H}$，使得如果 G $G$ 是 H $H$-free，则 χ ( G ) ≤ f H ( ω ( G ) ) $\chi (G)\le {f}_{H}(\omega (G))$ （其中 χ 、 ω $\chi 、\omega $ 是色数和 G $G$ 的团数）。 Louis Esperet 推测，只要这样的陈述成立，f H ${f}_{H}$ 就可以被选为多项式。已知 Gyárfás-Sumner 猜想仅适用于少量森林 H $H$，而 Esperet 猜想几乎不适用于任何森林。例如，不知道 H $H$ 何时是五顶点路径。这里我们证明当H$H$的每个分量都是星时Esperet的猜想。
The Gyárfás–Sumner conjecture says that for every forest H $H$, there is a function f H ${f}_{H}$ such that if G $G$ is H $H$‐free then χ ( G ) ≤ f H ( ω ( G ) ) $\chi (G)\le {f}_{H}(\omega (G))$ (where χ , ω $\chi ,\omega $ are the chromatic number and the clique number of G $G$). Louis Esperet conjectured that, whenever such a statement holds, f H ${f}_{H}$ can be chosen to be a polynomial. The Gyárfás–Sumner conjecture is only known to be true for a modest set of forests H $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when H $H$ is a five‐vertex path. Here we prove Esperet's conjecture when each component of H $H$ is a star.
登录
查看更多内容
DOI：
10.1016/0012-365x(80)90230-7
发表时间：
1980
期刊：
Discret. Math.
影响因子：
--
作者：
A. Gyárfás;E. Szemerédi;Z. Tuza
通讯作者：
A. Gyárfás;E. Szemerédi;Z. Tuza
具有大色数的图的归纳子图 VII。
DOI：
--
发表时间：
2017
期刊：
Journal of combinatorial theory. Series B (Print)
影响因子：
--
作者：
A. Scott;P. Seymour
通讯作者：
P. Seymour
影响因子：
0.9
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
通讯作者：
Spirkl, Sophie
DOI：
10.1002/jgt.3190180203
发表时间：
1994-03
期刊：
J. Graph Theory
影响因子：
--
作者：
H. Kierstead;S. Penrice
通讯作者：
H. Kierstead;S. Penrice
DOI：
10.1137/s0895480198339869
发表时间：
2004-04
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
H. Kierstead;Yingxian Zhu
通讯作者：
H. Kierstead;Yingxian Zhu