Disjoint K_{\mathrm{4}}^{-} in claw-free graphs with minimum degree at least five

Abstract

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_1,3. Let K_{\mathrm{4}}^{-} be the graph obtained by removing exactly one edge from K₄ and let k be an integer with k\ge \mathrm{2}. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K_{\mathrm{4}}^{-}. The requirement of number five is necessary.

Keywords

Forbidden graph / vertex-disjoint subgraph / minimum degree

References

[1] Bondy J A, Murty U S R. Graph Theory. 2nd ed. New York: Springer, 2008

[2] Fujita S. Disjoint stars and forbidden subgraphs. Hiroshima Math J, 2006, 36: 397-403

[3] Fujita S. Vertex-disjoint copies of K1+ (K₁∪K₂ ) in claw-free graphs. Discrete Math, 2008, 308(6): 1628-1633

[4] Kawarabayashi K. F-factor and vertex-disjoint F in a graph. Ars Combin, 2002, 62: 183-187

[5] Kawarabayashi K. K4--factor in graphs. J Graph Theory, 2002, 39: 111-128

[6] Wang H. Vertex-disjoint triangles in claw-free graphs with minimum degree at least three. Combinatorica, 1998, 18(3): 441-447

[7] Zhang X, Li N, Wu J L, Yan J. Vertex-disjoint triangles in K_1,t-free graphs with minimum degree at least t. Discrete Math, 2010, 310(19): 2499-2503

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg