Cycles in triangle-free graphs of large chromatic number
Cycles in triangle-free graphs of large chromatic number
复制标题
DOI：
10.1007/s00493-015-3262-0
复制
发表时间：
2014-04
期刊：
影响因子：
1.1
通讯作者：
A. Kostochka;B. Sudakov;Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
A. Kostochka;B. Sudakov;Jacques Verstraëte
早在二十多年前Erdős就推测出了一个色数k≥k0（ε）的无三角形图g0包含至少k2−ε不同长度的环（问→∞）。本文证明了色数k≥k0（ε）的无三角形图g包含一个连续长度为1/64(1−ε)k2logk/4的循环，且至少包含一个长度为1/4(1−ε)k2logk的循环。由于存在色数的无三角形图，最多有大约4k2logk个顶点，因此这些结果严格到一个常数因子。在其他单调类中，特别是无叉图和无奇圈图，给出了叉色图的周长和不同圈长的个数的新下界。
More than twenty years ago Erdős conjectured [4] that a triangle-free graphGof chromatic numberk≥k0(ε) contains cycles of at leastk2−εdifferent lengths ask→∞. In this paper, we prove the stronger fact that every triangle-free graphGof chromatic numberk≥k0(ε) contains cycles of 1/64(1 −ε)k2logk/4 consecutive lengths, and a cycle of length at least 1/4(1 −ε)k2logk. As there exist triangle-free graphs of chromatic numberkwith at most roughly 4k2logkvertices for largek, these results are tight up to a constant factor. We also give new lower bounds on the circumference and the number of different cycle lengths fork-chromatic graphs in other monotone classes, in particular, forKr-free graphs and graphs without odd cyclesC2s+1.