Cycles with consecutive odd lengths

DOI10.1016/J.EJC.2015.09.002zbMATH Open1327.05175OpenAlexW1884418294MaRDI QIDQ896065FDOQ896065

Authors Jie Ma

Publication date 11 December 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

non-bipartite 2-connected graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Paths and cycles (05C38) Connectivity (05C40)

Abstract: It is proved that there exists an absolute constant c > 0 such that for every natural number k, every non-bipartite 2-connected graph with average degree at least ck contains k cycles with consecutive odd lengths. This implies the existence of the absolute constant d > 0 that every non-bipartite 2-connected graph with minimum degree at least dk contains cycles of all lengths modulo k, thus providing an answer (in a strong form) to a question of Thomassen. Both results are sharp up to the constant factors.

Recommendations

• Cycle lengths and minimum degree of graphs
• A unified proof of conjectures on cycle lengths in graphs
• Distribution of cycle lengths in graphs
• scientific article; zbMATH DE number 867704
• Cycles of even lengths modulo \(k\)

Cites work

• scientific article; zbMATH DE number 4077268 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• Another Simple Proof of the High Girth, High Chromatic Number Theorem
• Cycle lengths in sparse graphs
• Cycles Modulo k
• Cycles of even lengths modulo \(k\)
• Cycles of length 0 modulo 4 in graphs
• Distribution of cycle lengths in graphs
• Dynamic cage survey
• Girth in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• On a valence problem in extremal graph theory
• On arithmetic progressions of cycle lengths in graphs
• On the chromatic number of pentagon-free graphs of large minimum degree
• The chromatic thresholds of graphs

Cited in

(10)

• Cycles of even lengths modulo \(k\)
• A strengthening on odd cycles in graphs of given chromatic number
• Linear cycles of consecutive lengths
• On two cycles of consecutive even lengths
• Unavoidable cycle lengths in graphs
• Cycle lengths and minimum degree of graphs
• Cycles of given lengths in hypergraphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• A solution to Erdős and Hajnal’s odd cycle problem

This page was built for publication: Cycles with consecutive odd lengths

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