论文标题
给定色数的图中奇数循环的增强
A strengthening on odd cycles in graphs of given chromatic number
论文作者
论文摘要
Gyárfás解决了Bollobás和Erdős的猜想，证明了每张图$ g $的色度$ k+k+1 \ 1 \ geq 3 $包含$ \ lfloor \ lfloor \ frac {k} {k} {2} {2} \ rfloor $不同的奇数长度。我们通过证明这种$ g $包含$ \ lfloor \ frac {k} {2} {2} \ rfloor $ regation octected奇数长度的周期来增强这一突出的结果。一路上结合了极端和结构工具，我们证明了一个更强有力的声明，即每图$ k+1 \ 1 \ geq 7 $都包含连续长度的$ k $循环，只是某个块为$ k_ {k+1} $。作为推论，这证实了Verstraëte的猜想，并回答了Moore和West的问题。
Resolving a conjecture of Bollobás and Erdős, Gyárfá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ëte and answers a question of Moore and West.
