Disjoint cycles in graphs with restricted independence number (Q2166216)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Disjoint cycles in graphs with restricted independence number
scientific article

    Statements

    Disjoint cycles in graphs with restricted independence number (English)
    0 references
    0 references
    0 references
    24 August 2022
    0 references
    \textit{H. A. Kierstead} et al. [J. Comb. Theory, Ser. B 122, 121--148 (2017; Zbl 1350.05072)] showed that, for \(k\geq 3\), every graph with \(n\geq 3k\) vertices, minimum degree at least \(2k-1\) and independence number at most \(n-2k-1\) has \(k\) vertex-disjoint cycles. In this paper, the authors extend the above result by showing that there exist \(\beta>0\) and \(t_0\) such that for every \(t\geq t_0\), \(k\geq 25t\) and \(n\geq 4k+t\), every graph on \(n\) vertices with minimum degree at least \(2k-t\) and independence number at most \(n-2k-t+\beta\sqrt{t\log t}\) contains \(k\) vertex-disjoint cycles.
    0 references
    0 references
    extremal graph theory
    0 references
    cycles
    0 references
    paths
    0 references

    Identifiers