Cycles with consecutive odd lengths
From MaRDI portal
Publication:896065
DOI10.1016/J.EJC.2015.09.002zbMATH Open1327.05175arXiv1410.0430OpenAlexW1884418294MaRDI QIDQ896065FDOQ896065
Publication date: 11 December 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1410.0430
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On arithmetic progressions of cycle lengths in graphs
- Cycles of length 0 modulo 4 in graphs
- On a valence problem in extremal graph theory
- Graph decomposition with applications to subdivisions and path systems modulo k
- Dynamic cage survey
- Cycle lengths in sparse graphs
- On the chromatic number of pentagon-free graphs of large minimum degree
- Girth in graphs
- The chromatic thresholds of graphs
- Distribution of cycle lengths in graphs
- Cycles of even lengths modulo k
- Cycles Modulo k
- Another Simple Proof of the High Girth, High Chromatic Number Theorem
Cited In (7)
- Linear cycles of consecutive lengths
- A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
- The extremal function for cycles of length \(\ell\) mod \(k\)
- Cycle lengths and minimum degree of graphs
- A solution to Erdős and Hajnal’s odd cycle problem
- Cycle Lengths Modulo k in Large 3-connected Cubic Graphs, Advances in Combinatorics
- Cycles of given lengths in hypergraphs
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)
