Stability in the Erdős–Gallai Theorems on cycles and paths: Dedicated to the memory of G.N. Kopylov

Zoltán Füredi, Alexandr Kostochka, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

Abstract

The Erdős–Gallai Theorem states that for k≥2, every graph of average degree more than k−2 contains a k-vertex path. This result is a consequence of a stronger result of Kopylov: if k is odd, k=2t+1≥5, n≥(5t−3)/2, and G is an n-vertex 2-connected graph with at least h(n,k,t):=(k−t2)+t(n−k+t) edges, then G contains a cycle of length at least k unless G=Hn,k,t:=Kn−E(Kn−t). In this paper we prove a stability version of the Erdős–Gallai Theorem: we show that for all n≥3t>3, and k∈{2t+1,2t+2}, every n-vertex 2-connected graph G with e(G)>h(n,k,t−1) either contains a cycle of length at least k or contains a set of t vertices whose removal gives a star forest. In particular, if k=2t+1≠7, we show G⊆Hn,k,t. The lower bound e(G)>h(n,k,t−1) in these results is tight and is smaller than Kopylov's bound h(n,k,t) by a term of n−t−O(1).

Original languageEnglish (US)
Pages (from-to)197-228
Number of pages32
JournalJournal of Combinatorial Theory. Series B
Volume121
DOIs
StatePublished - Nov 1 2016

Keywords

  • Cycles
  • Paths
  • Turán problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Stability in the Erdős–Gallai Theorems on cycles and paths: Dedicated to the memory of G.N. Kopylov'. Together they form a unique fingerprint.

Cite this