Polynomial χ-binding functions for t-broom-free graphs
Polynomial χ-binding functions for t-broom-free graphs
复制标题
无 t-broom 图的多项式 Ï 绑定函数
DOI：
10.1016/j.jctb.2023.04.005
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yu, Xingxing
中科院分区：
文献类型：
--
作者：
Liu, Xiaonan;Schroeder, Joshua;Wang, Zhiyu;Yu, Xingxing
对于任意正整数t， t扫把是由K （1, t+ 1）将一条边细分一次得到的图。在本文中，我们证明了对于没有诱导t-broom的图G，我们有χ (G)= o (ω (G) t+ 1)，其中χ (G)和ω (G)分别是G的色数和团数。当t= 2时，这回答了Schiermeyer和Randerath的问题。此外，当t= 2时，我们将χ (G)的界强化为7 ω (G) 2，证实了Sivaraman的一个猜想。对于t≥3和{t-broom， K t， t}自由图，我们将边界改进为0 （ω t）。
For any positive integer t, a t-broom is a graph obtained from K 1, t+ 1 by subdividing an edge once. In this paper, we show that, for graphs G without induced t-brooms, we have χ (G)= o (ω (G) t+ 1), where χ (G) and ω (G) are the chromatic number and clique number of G, respectively. When t= 2, this answers a question of Schiermeyer and Randerath. Moreover, for t= 2, we strengthen the bound on χ (G) to 7 ω (G) 2, confirming a conjecture of Sivaraman. For t≥ 3 and {t-broom, K t, t}-free graphs, we improve the bound to o (ω t).
登录
查看更多内容
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
无诱导叉的无平方图
DOI：
10.37236/9144
发表时间：
2021
期刊：
The Electronic Journal of Combinatorics
影响因子：
--
作者：
Chudnovsky, Maria;Huang, Shenwei;Karthick, T.;Kaufmann, Jenny
通讯作者：
Kaufmann, Jenny
影响因子：
0.9
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
通讯作者：
Spirkl, Sophie
通过完美可分性对没有诱导分叉的图类进行着色
影响因子：
0.7
作者：
T. Karthick;Jenny Kaufmann;Vaidy Sivaraman
通讯作者：
Vaidy Sivaraman
DOI：
10.1002/jgt.3190180203
发表时间：
1994-03
期刊：
J. Graph Theory
影响因子：
--
作者：
H. Kierstead;S. Penrice
通讯作者：
H. Kierstead;S. Penrice