A Unified Proof of Conjectures on Cycle Lengths in Graphs
A Unified Proof of Conjectures on Cycle Lengths in Graphs
复制标题
DOI：
10.1093/imrn/rnaa324
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Jun-ming Gao;Qingyi Huo;Chun-Hung Liu;Jie Ma
中科院分区：
文献类型：
--
作者：
Jun-ming Gao;Qingyi Huo;Chun-Hung Liu;Jie Ma
本文证明了一般图中两个给定端点之间存在路的一个最小度紧条件，这两个端点的长度构成一个公差为1或2的长等差数列.这使我们能够获得一些确切的和最佳的结果圈长度的图的最小度，连通性或色数。更确切地说，我们用统一的方法证明了以下陈述。(1)每一个最小度至少为k+1的图G都包含模k的所有偶数长度的圈;此外，如果G是2-连通的非二部图，则它包含模k的所有长度的圈。(2)对于所有的$k\geq 3$，每个$k$-连通图包含一个模$k$长度为零的圈。(3)每一个最小度至少为k+1的3连通非二部图都含有k个长度连续的圈。(4)每一个色数至少为k+2的图都含有k个长度连续的圈.第一种说法是一个猜想的Mallassen，第二个是一个猜想的迪恩，第三个是一个严格的答案，一个问题的邦迪和文斯，第四个是一个猜想的Sudakov和Verstraete。上述所有结果都是最好的。
In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints, whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach. (1) Every graph $G$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $k$; in addition, if $G$ is 2-connected and non-bipartite, then it contains cycles of all lengths modulo $k$. (2) For all $k\geq 3$, every $k$-connected graph contains a cycle of length zero modulo $k$. (3) Every 3-connected non-bipartite graph with minimum degree at least $k+1$ contains $k$ cycles of consecutive lengths. (4) Every graph with chromatic number at least $k+2$ contains $k$ cycles of consecutive lengths. The first statement is a conjecture of Thomassen, the second is a conjecture of Dean, the third is a tight answer to a question of Bondy and Vince, and the fourth is a conjecture of Sudakov and Verstraete. All of the above results are best possible.