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
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
extremal graph theory
0 references
cycles
0 references
paths
0 references
0 references