Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903895 | Journal of Combinatorial Theory, Series B | 2018 | 30 Pages |
Abstract
Thomassen (1983) made two conjectures on cycle lengths modulo a fixed integer k: (1) every graph with minimum degree at least k+1 contains cycles of all even lengths modulo k; (2) every 2-connected non-bipartite graph with minimum degree at least k+1 contains cycles of all lengths modulo k. These two conjectures, if true, are best possible. Our results confirm both conjectures when k is even. When k is odd, we show that minimum degree at least k+4 suffices. This improves all previous results in this direction. Moreover, our results derive new upper bounds of the chromatic number in terms of the longest sequence of cycles with consecutive (even or odd) lengths.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Chun-Hung Liu, Jie Ma,