Cycle lengths and minimum degree of graphs

DOI10.1016/J.JCTB.2017.08.002zbMATH Open1375.05152arXiv1508.07912OpenAlexW2963120913MaRDI QIDQ1682209FDOQ1682209

Authors: Chun-Hung Liu, Jie Ma 

Publication date: 28 November 2017

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

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.

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

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

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)

Cites Work

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

Cited In (35)

• 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
• Congruence of cycle lengths and chromatic number
• Minimum cycle partition with length requirements
• Cycle lengths modulo \(k\) in expanders
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycles of even lengths modulo \(k\)
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Cycle lengths and chromatic number of graphs
• Cycle lengths in sparse graphs
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• Title not available (Why is that?)
• Chvátal-Erdős condition for pancyclicity
• Minimum number of edges that occur in odd cycles
• Coloring graphs with two odd cycle lengths
• On two cycles of consecutive even lengths
• Cycle-saturated graphs of minimum size
• Cycles of length 0 modulo 4 in graphs
• Alternating paths and cycles of minimum length
• Cycle lengths in expanding graphs
• A note on cycle lengths in graphs
• On a conjecture of Bondy and Vince
• Linear cycles of consecutive lengths
• Modularity of cycles and paths in graphs
• Properly colored cycles of different lengths in edge-colored complete graphs
• On arithmetic progressions of cycle lengths in graphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• A unified proof of conjectures on cycle lengths in graphs
• Cycle lengths in graphs with large minimum degree
• Title not available (Why is that?)
• A solution to Erdős and Hajnal’s odd cycle problem
• Cycles with consecutive odd lengths
• Cycles of given lengths in hypergraphs

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)