On Arithmetic Progressions of Cycle Lengths in Graphs
From MaRDI portal
Publication:2703026
DOI10.1017/S0963548300004478zbMATH Open0978.05043arXivmath/0204222OpenAlexW1992473680MaRDI QIDQ2703026
Publication date: 21 January 2002
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Abstract: A recently posed question of Haggkvist and Scott's asked whether or not there exists a constant c such that if G is a graph of minimum degree ck then G contains cycles of k consecutive even lengths. In this paper we answer the question by proving that for k > 1, a bipartite graph of average degree at least 4k and girth g contains cycles of (g/2-1)k consecutive even lengths. We also obtain a short proof of the theorem of Bondy and Simonovits, that a graph of order n and size at least 8(k-1)n^{1 + 1/k} has a cycle of length 2k.
Full work available at URL: https://arxiv.org/abs/math/0204222
Related Items (45)
The number of \(C_{2\ell}\)-free graphs ⋮ Cycle lengths and minimum degree of graphs ⋮ Linear cycles of consecutive lengths ⋮ On the spectrum of Wenger graphs ⋮ Bipartite-ness under smooth conditions ⋮ Making an H $H$‐free graph k $k$‐colorable ⋮ On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles ⋮ Cycles with consecutive odd lengths ⋮ Hamilton cycles in highly connected and expanding graphs ⋮ A solution to Erdős and Hajnal’s odd cycle problem ⋮ How to build a pillar: a proof of Thomassen's conjecture ⋮ Extremal numbers of hypergraph suspensions of even cycles ⋮ A Bound on the Number of Edges in Graphs Without an Even Cycle ⋮ Nearly bipartite graphs ⋮ On a conjecture of Erdős and Simonovits: even cycles ⋮ Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs ⋮ Linked graphs with restricted lengths ⋮ A Conjecture of Verstraëte on Vertex-Disjoint Cycles ⋮ Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers ⋮ The spectral even cycle problem ⋮ The spectral radius of graphs with no odd wheels ⋮ Cycles in triangle-free graphs of large chromatic number ⋮ Parity check matrices and product representations of squares ⋮ On some cycles in Wenger graphs ⋮ Cycle lengths in sparse graphs ⋮ A Strengthening on Odd Cycles in Graphs of Given Chromatic Number ⋮ The extremal function for cycles of length \(\ell\) mod \(k\) ⋮ On 3-uniform hypergraphs without a cycle of a given length ⋮ Cycle Lengths Modulo k in Large 3-connected Cubic Graphs, Advances in Combinatorics ⋮ Pancyclicity of Hamiltonian and highly connected graphs ⋮ A note on short cycles in a hypercube ⋮ On a conjecture of Bondy and Vince ⋮ Cycles of given lengths in hypergraphs ⋮ Cycle lengths in expanding graphs ⋮ Cycles of even lengths modulo k ⋮ Spectral extremal problem on \(t\) copies of \(\ell\)-cycles ⋮ On an extremal hypergraph problem related to combinatorial batch codes ⋮ The extremal function for two disjoint cycles ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ Unnamed Item ⋮ Hypergraphs with Few Berge Paths of Fixed Length between Vertices ⋮ Supersaturation of even linear cycles in linear hypergraphs ⋮ Turán numbers of theta graphs ⋮ A note on the Turán function of even cycles ⋮ Cycle lengths modulo \(k\) in expanders
This page was built for publication: On Arithmetic Progressions of Cycle Lengths in Graphs
