Cycle lengths and minimum degree of graphs

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.