A STABILITY RESULT OF THE POSA LEMMA*

Jie Ma, Long Tu Yuan

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

For an integer \alpha and a graph G, the \alpha-disintegration of G is the graph obtained from G by recursively deleting vertices of degree at most \alpha until the resulting graph has no such vertex. P\'osa proved that if a 2-connected graph contains a path on m \geq k vertices with end-vertices in its \lfloor(k-1)/2\rfloor-disintegration, then G contains a cycle of length at least k. We prove that if a 2-connected graph contains a path on m \geq k vertices with end-vertices in its \lfloor(k - 3)/2\rfloor-disintegration, then G contains either a cycle of length at least k or a specific family of graphs. As an application, we strengthen the Erd\Hos-Gallai stablity theorem of F\" uredi, Kostochka, Luo, and Verstra\"ete.

Original languageEnglish
Pages (from-to)1757-1783
Number of pages27
JournalSIAM Journal on Discrete Mathematics
Volume38
Issue number2
DOIs
StatePublished - 2024

Keywords

  • P\'osa lemma
  • cycles
  • stability

Fingerprint

Dive into the research topics of 'A STABILITY RESULT OF THE POSA LEMMA*'. Together they form a unique fingerprint.

Cite this