Back to Search
Start Over
A STABILITY RESULT OF THE PÓSA LEMMA.
- 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 :
- INTEGERS
Subjects
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