Back to Search Start Over

A STABILITY RESULT OF THE PÓSA LEMMA.

Authors :
JIE MA
LONG-TU YUAN
Source :
SIAM Journal on Discrete Mathematics; 2024, Vol. 38 Issue 2, p1757-1783, 27p
Publication Year :
2024

Abstract

For an integer a and a graph G, the a-disintegration of G is the graph obtained from G by recursively deleting vertices of degree at most a until the resulting graph has no such vertex. Pósa proved that if a 2-connected graph contains a path on m ≥ k vertices with end-vertices in its ⌊(k-1)2]⌋disintegration, then G contains a cycle of length at least k. We prove that if a 2-connected graph contains a path on m ≥ k vertices with end-vertices in its ⌊(k-3)/2⌋-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ös--Gallai stablity theorem of Füredi, Kostochka, Luo, and Verstraëte. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
INTEGERS

Details

Language :
English
ISSN :
08954801
Volume :
38
Issue :
2
Database :
Complementary Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
178602080
Full Text :
https://doi.org/10.1137/20M1382143