A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
复制标题
DOI：
10.1137/20m1387882
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Jun-ming Gao;Qingyi Huo;Jie Ma
中科院分区：
文献类型：
--
作者：
Jun-ming Gao;Qingyi Huo;Jie Ma
解决了Bollob\'{a}s和Erd\H{o}s的一个猜想，戈伊\'{a}rf\'{a}s证明了色数为k+1\geq 3$的图G$包含$\lfloor\frac{k}{2}\rfloor$不同奇长的圈.我们加强这一突出的结果表明，这样的$G$包含循环的$\lfloor\frac{k}{2}\rfloor$连续奇数长度。沿着的方式，结合极值和结构工具，我们证明了一个更强的声明，每个图的色数$k+1\geq 7$包含$k$圈的连续长度，除了一些块是$K_{k+1}$。作为推论，这证实了Verstra\“埃特的一个猜想，并回答了摩尔和韦斯特的一个问题。
Resolving a conjecture of Bollob\'{a}s and Erd\H{o}s, Gy\'{a}rf\'{a}s proved that every graph $G$ of chromatic number $k+1\geq 3$ contains cycles of $\lfloor\frac{k}{2}\rfloor$ distinct odd lengths. We strengthen this prominent result by showing that such $G$ contains cycles of $\lfloor\frac{k}{2}\rfloor$ consecutive odd lengths. Along the way, combining extremal and structural tools, we prove a stronger statement that every graph of chromatic number $k+1\geq 7$ contains $k$ cycles of consecutive lengths, except that some block is $K_{k+1}$. As corollaries, this confirms a conjecture of Verstra\"ete and answers a question of Moore and West.