Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs (Q844222): Difference between revisions

For a graph \(G\), denote \(|V(G)|\) by \(n(G)\), the minimum degree of \(G\) by \(\delta(G)\), and the minimum number of components in a \(2\)-factor of \(G\) by \(f_2(G)\). Improving results of \textit{R. Faudree}, \textit{O. Favaron}, \textit{E. Flandrin}, \textit{H. Li}, and \textit{Z. Liu} [``On 2-factors in claw-free graphs,'' Discrete Math. 206, No.1-3, 131--137 (1999; Zbl 0981.05084)] and \textit{R. Gould} and \textit{M. Jacobson} [``Two-factors with few cycles in claw-free graphs,'' Discrete Math. 231, No.1-3, 191--197 (2001; Zbl 0979.05084)], the authors prove the following two theorems. If \(G\) is claw-free with \(\delta(G) = 4\), then \(f_2(G) \leq (5n(G) - 14)/18\) unless \(G\) belongs to a finite class of exceptional graphs. If \(G\) is claw-free with \(\delta(G) \geq 5\), then \(f_2(G) \leq \max \{ 1, (n(G) - 3)/(\delta(G) - 1) \}\). Their theorems give an affirmative answers to open problems posed by the third author [``On the number of components in 2-factors of claw-free graphs,'' Discrete Math. 307, No.\,22, 2808--2819 (2007; Zbl 1129.05037)]. Also their bounds are best possible in a sense since the third author [loc. cit.] provided an infinite family \(\{ H_i \}\) of claw-free graphs with \(\delta(H_i) = 4\) such that \(\lim_{n(H_i) \rightarrow \infty} f_2(H_i) / n(H_i) = 5/18\) and for each \(d \geq 4\), an infinite family \(\{ F_i^d \}\) of claw-free graphs with \(\delta(F_i^d) \geq d\) and \(f_2(F_i^d) > n(F_i^d)/\delta(F_i^d)\). The authors pose an open problem: Does every \(2\)-connected claw-free graph \(G\) have a \(2\)-factor with at most \(n(G)/(3\delta(G))\) components? They also restate another open problem posed by the third author [loc. cit.]: Does every bridgeless claw-free graph \(G\) have \(f_2(G) \leq (n(G)-1)/\delta(G)\)?