Independence number and vertex-disjoint cycles
type: Item
instance of: scholarly article
title: Independence number and vertex-disjoint cycles
zbMATH Open document ID: 1117.05080
author: Yoshimi Egawa
author: Hikoe Enomoto
author: Katsuhiro Ota
author: Ingo Schiermeyer
author: Stanislav Jendroľ
published in: Discrete Mathematics
publication date: 2007-04-26T00:00:00Z
review text: 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.
reviewed by: Brigitte Servatius
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5146849
MaRDI profile type: Publication
full work available at URL: j.disc.2005.11.086
OpenAlex ID: W2052169294
cites work: Q5422499
cites work: On the maximal number of independent circuits in a graph
cites work: Vertex-disjoint cycles of the same length
cites work: On the existence of disjoint cycles in a graph
cites work: Graph Theory and Probability
cites work: On the maximum number of independent cycles in a graph
DOI: 10.1016/J.DISC.2005.11.086
description: scientific article; zbMATH DE number 5146849