Independence number and vertex-disjoint cycles (Q878646)

For given integers \(k\) and \(\alpha\), let \(f(k, \alpha)\) be the maximum order of a (finite simple) graph \(G\) with independence number \(\alpha (G) \leq \alpha\), which has no \(k\) vertex-disjoint cycles. The authors present constructive sharp lower bounds for \(f(k, \alpha)\) and derive upper bounds using Ramsey numbers. It is shown that \(f(k, \alpha ) \geq 3k+2\alpha -3\) and that equality holds for \(\alpha\) between 1 and 5, or \(k\) between 1 and 2. Moreover, the existence of constants \(c_{\alpha}\) (depending only on \(\alpha\)) and \(t_k\) (depending only on \(k\)) such that \(f(k, \alpha)\) is bounded from above by \(3k+c_{\alpha}\), or \(2\alpha +t_k\) respectively, is established, but it is shown there exists no absolute constant \(c\) such that \(f(k, \alpha) \leq c(k+\alpha )\). The finding of an explicit pair of integers \(k\) and \(\alpha \) such that \(f(k, \alpha) > 3k +2\alpha - 3\) is left as a challenging open problem.