Disjoint cycles in graphs with restricted independence number
2022
In 1963, Corrádi and Hajnal proved that every graph with at least vertices and minimum degree at least contains a collection of vertex-disjoint cycles. The sharpness examples for this theorem were characterized by Kierstead, Kostochka, and Yeager in 2017 and one consequence of this characterization is that when , every graph with vertices, minimum degree at least , and independence number at most has vertex-disjoint cycles. We extend this result by showing that there exists and such that for every , and , every graph on vertices with minimum degree at least and independence number at most contains a collection of vertex-disjoint cycles. We also show that the condition on the independence number is sharp up to the constant .
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI