A unified proof of conjectures on cycle lengths in graphs

DOI10.1093/IMRN/RNAA324MaRDI QIDQ5082279zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

pathscycles

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cited in

(14)

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

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)