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

minimum degreeThomassen's conjecturecycle length modulo \(k\)cycles of consecutive lengths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) 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

• 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?)
• 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 Modulo k
• Cycles and paths in graphs with large minimal degree
• Cycles in triangle-free graphs of large chromatic number
• 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
• 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

(35)

• Modularity of cycles and paths in graphs
• Cycles of even lengths modulo \(k\)
• Cycle-saturated graphs of minimum size
• Coloring graphs with two odd cycle lengths
• Cycle lengths in sparse graphs
• Minimum number of edges that occur in odd cycles
• On arithmetic progressions of cycle lengths in graphs
• A unified proof of conjectures on cycle lengths in graphs
• Chvátal-Erdős condition for pancyclicity
• Cycle lengths and chromatic number of graphs
• Congruence of cycle lengths and chromatic number
• Cycles of length 0 modulo 4 in graphs
• A strengthening on odd cycles in graphs of given chromatic number
• Cycle lengths in graphs with large minimum degree
• Linear cycles of consecutive lengths
• On two cycles of consecutive even lengths
• Minimum cycle partition with length requirements
• Cycle lengths modulo \(k\) in expanders
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Cycles with consecutive odd lengths
• scientific article; zbMATH DE number 1033814 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 6692113 (Why is no real title available?)
• scientific article; zbMATH DE number 4154477 (Why is no real title available?)
• scientific article; zbMATH DE number 151768 (Why is no real title available?)
• A note on cycle lengths in graphs
• Cycles of given lengths in hypergraphs
• Alternating paths and cycles of minimum length
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• Cycle lengths in expanding graphs
• A solution to Erdős and Hajnal’s odd cycle problem
• Properly colored cycles of different lengths in edge-colored complete graphs
• On a conjecture of Bondy and Vince

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)