A Stability Result of the Pósa Lemma
Jie Ma, Long-Tu Yuan
Source abstract
Abstract. For an integer [Formula: see text] and a graph [Formula: see text], the [Formula: see text] -disintegration of [Formula: see text] is the graph obtained from [Formula: see text] by recursively deleting vertices of degree at most [Formula: see text] until the resulting graph has no such vertex. Pósa proved that if a 2-connected graph contains a path on [Formula: see text] vertices with end-vertices in its [Formula: see text]-disintegration, then [Formula: see text] contains a cycle of length at least [Formula: see text]. We prove that if a 2-connected graph contains a path on [Formula: see text] vertices with end-vertices in its [Formula: see text]-disintegration, then [Formula: see text] contains either a cycle of length at least [Formula: see text] 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.