Polynomial bounds for chromatic number. III. Excluding a double star
Polynomial bounds for chromatic number. III. Excluding a double star
复制标题
色数的多项式界限。
DOI：
10.1002/jgt.22862
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
“双星星星”是一棵树有两个内部顶点。已知Gyárfás-Sumner猜想对双星成立，即对每一双星星星H $H$，存在函数fH ${f}_{H}$使得如果G $G$不包含H $H$作为导出子图，则χ（G）≤ fH（ω（G））$\chi（G）\le {f}_{H}（\omega（G））$（其中χ，ω $\chi，\omega $是G $G$的色数和团数）。在这里，我们证明f H ${f}_{H}$可以被选择为多项式。
A “double star” is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star H $H$, there is a function f H ${f}_{H}$ such that if G $G$ does not contain H $H$ as an induced subgraph 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$). Here we prove that f H ${f}_{H}$ can be chosen to be a polynomial.
登录
查看更多内容
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
色数 II 的多项式界限：排除星形森林
影响因子：
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
DOI：
10.1016/j.ejc.2019.103024
发表时间：
2018-07
期刊：
Eur. J. Comb.
影响因子：
--
作者：
A. Scott;P. Seymour
通讯作者：
A. Scott;P. Seymour