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 language | English |
|---|---|
| Pages (from-to) | 1757-1783 |
| Number of pages | 27 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 38 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2024 |
Keywords
- P\'osa lemma
- cycles
- stability