A unified proof of conjectures on cycle lengths in graphs

DOI10.1093/IMRN/RNAA324zbMATH Open1496.05040arXiv1904.08126OpenAlexW3120197697WikidataQ123014072 ScholiaQ123014072MaRDI QIDQ5082279FDOQ5082279

Authors: Jun Gao, Qingyi Huo, Chun-Hung Liu, Jie Ma 

Publication date: 16 June 2022

Published in: IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Abstract: 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 $kgeq3$, 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 Verstra"ete. All of the above results are best possible.

Full work available at URL: https://arxiv.org/abs/1904.08126

Recommendations

• Cycle lengths and minimum degree of graphs
• Cycles of even lengths modulo \(k\)
• Distribution of cycle lengths in graphs
• scientific article
• Cycle lengths in graphs with large minimum degree

zbMATH Keywords

pathscycles

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Cited In (14)

• A strengthening on odd cycles in graphs of given chromatic number
• Minimum degree conditions for the existence of a sequence of cycles whose lengths differ by one or two
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Cycles and paths in graphs with large minimal degree
• How to build a pillar: a proof of Thomassen's conjecture
• Cycles of many lengths in Hamiltonian graphs
• On a conjecture of Bondy and Vince
• Linear cycles of consecutive lengths
• A simple proof of the multiplicativity of directed cycles of prime power length
• Divisible subdivisions
• On arithmetic progressions of cycle lengths in graphs
• A unified Erdős-Pósa theorem for constrained cycles
• Cycle lengths and minimum degree of graphs
• Cycles with consecutive odd lengths

This page was built for publication: A unified proof of conjectures on cycle lengths in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5082279)