Cycle lengths and minimum degree of graphs

DOI10.1016/J.JCTB.2017.08.002MaRDI QIDQ1682209zbMATH OpenOpenAlexFDO

Authors Chun-Hung Liu, Jie Ma

Publication date 28 November 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

cycle length modulo \(k\)cycles of consecutive lengthsminimum degreeThomassen's conjecture

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: There has been extensive research on cycle lengths in graphs with large minimum degree. In this paper, we obtain several new and tight results in this area. Let $G$ be a graph with minimum degree at least $k+1$. We prove that if $G$ is bipartite, then there are $k$ cycles in $G$ whose lengths form an arithmetic progression with common difference two. For general graph $G$, we show that $G$ contains $lfloork/2floor$ cycles with consecutive even lengths and $k-3$ cycles whose lengths form an arithmetic progression with common difference one or two. In addition, if $G$ is 2-connected and non-bipartite, then $G$ contains $lfloork/2floor$ cycles with consecutive odd lengths. 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. And 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.

Recommendations

• A unified proof of conjectures on cycle lengths in graphs
• scientific article; zbMATH DE number 6692113
• Cycles of even lengths modulo k
• Cycle lengths in graphs with large minimum degree
• Cycles with consecutive odd lengths

Cites work

• A note on cycle lengths in graphs
• Circumference, chromatic number and online coloring
• Coloring digraphs with forbidden cycles
• Cycle lengths and chromatic number of graphs
• Cycle lengths in graphs with large minimum degree
• Cycle lengths in sparse graphs
• Cycles and paths in graphs with large minimal degree
• Cycles in triangle-free graphs of large chromatic number
• Cycles Modulo k
• Cycles of even length in graphs
• Cycles of even lengths modulo k
• Cycles of length 0 modulo 4 in graphs
• Cycles with consecutive odd lengths
• Distribution of cycle lengths in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• Graph theory
• Graphs with \(k\) odd cycle lengths
• Graphs with a cycle of length divisible by three
• scientific article; zbMATH DE number 4077268 (Why is no real title available?)
• scientific article; zbMATH DE number 3547317 (Why is no real title available?)
• scientific article; zbMATH DE number 3570494 (Why is no real title available?)
• scientific article; zbMATH DE number 554066 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 867704 (Why is no real title available?)
• Non-separating induced cycles in graphs
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On arithmetic progressions of cycle lengths in graphs
• On chromatic number of graphs and set-systems
• Pancyclic graphs. I
• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• Some Theorems on Abstract Graphs
• Special subdivisions of \(K_4\) and 4-chromatic graphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• The longest cycle of a graph with a large minimal degree
• Weakly pancyclic graphs

Cited in

(43)

• The number of cycle lengths in graphs of given minimum degree and girth
• Cycles of length 0 modulo 4 in graphs
• On cycle lengths in graphs of moderate degree
• Cycles of given lengths in hypergraphs
• A note on cycle lengths in graphs
• Cycle lengths and chromatic number of graphs
• Cycle-saturated graphs of minimum size
• Cycle lengths in expanding graphs
• Minimum cycle partition with length requirements
• Cycle lengths modulo k in expanders
• On a conjecture of Bondy and Vince
• Minimum number of edges that occur in odd cycles
• On arithmetic progressions of cycle lengths in graphs
• scientific article; zbMATH DE number 6692113 (Why is no real title available?)
• Cycles of even lengths modulo k
• Alternating paths and cycles of minimum length
• scientific article; zbMATH DE number 4154477 (Why is no real title available?)
• scientific article; zbMATH DE number 151768 (Why is no real title available?)
• Modularity of cycles and paths in graphs
• scientific article; zbMATH DE number 1033814 (Why is no real title available?)
• Coloring graphs with two odd cycle lengths
• A unified proof of conjectures on cycle lengths in graphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• A strengthening on odd cycles in graphs of given chromatic number
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• Cycle lengths in graphs with large minimum degree
• Linear cycles of consecutive lengths
• Properly colored cycles of different lengths in edge-colored complete graphs
• Minimum degree conditions for the existence of a sequence of cycles whose lengths differ by one or two
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Congruence of cycle lengths and chromatic number
• A solution to Erdős and Hajnal’s odd cycle problem
• On two cycles of consecutive even lengths
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Chvátal-Erdős condition for pancyclicity
• On graphs without cycles of length 0 modulo 4
• A generalization of Bondy's pancyclicity theorem
• A strengthening on consecutive odd cycles in graphs of given minimum degree
• Chvátal-Erdős condition for pancyclicity (extended abstract)
• A generalization of Bondy's pancyclicity theorem (extended abstract)
• Cycle lengths in graphs of given minimum degree
• Cycles with consecutive odd lengths
• Cycle lengths in sparse graphs

This page was built for publication: Cycle lengths and minimum degree of graphs

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