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
    []