Minimum degree and disjoint cycles in generalized claw-free graphs

作者：Faudree Ralph J^*; Gould Ronald J; Jacobson Michael S

来源：European Journal of Combinatorics, 2013, 34(5): 875-883.

DOI：10.1016/j.ejc.2012.12.002

For s %26gt;= 3 a graph is K-1,K-s-free if it does not contain an induced subgraph isomorphic to K-1,K-s. Cycles in K-1,K-3-free graphs, called claw-free graphs, have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions to K-1,K-s,-free graphs, normally called generalized claw-free graphs. In particular, we prove that if G is K1,-free of sufficiently large order n = 3k with 8(G) %26gt; n/2-1- c for some constant c = c(s), then G contains k disjoint triangles. Analogous results with the complete graph K3 replaced by a complete graph Km for m %26gt; 3 will be proved. Also, the existence of 2-factors for 1(1,0-free graphs with minimum degree conditions will be shown. Published by Elsevier Ltd

• 出版日期2013-7