Vertex disjoint copies of K1,4 in claw-free graphs

Highlights：

• Conjecture. Let k, r, t be integers with k≥2, r≥3 and t≥2. If G is a K1,r-free graph of order at least (k−1)(t(r−1)+1)+1 with δ(G)≥t, then G contains k disjoint K1,ts.

• The bound on |V(G)| is best possible if the conjecture is true. The conjecture has been confirmed in the following cases: t=2 (Fujita), r=t=3 (Fujita), r≥4 and t=3 (Jiang et al.), r≥2t−1 and t≥3 (Jiang et al.). Moreover Jiang, Chiba, Fujita and Yan gave a counterexample with |V(G)|=10k−10 for the conjecture when r=3,t=4, and they whether G contain k disjoint copies of K1,4 if G is a claw-free graph of order |V(G)|≥10k−9 with δ(G)≥4.

• In this paper, we answer this question by proving the following theorem. Theorem. Let k be an integer with k≥2. If G is a claw-free graph of order at least 10k−9 with δ(G)≥4, then G contains k disjoint K1,4s.

摘要

•Fujita investigated what kind of graphs should be excluded when consider the existence of disjoint K1,ts in a sparse graph, and answered this question: If there exists an integer N such that each H-free graph G of order |V(G)|≥N with δ(G)≥t contains k disjoint K1,ts, then H≅K1,r. On the other hand, motivated by this result, Fujita proposed the following conjecture.•Conjecture. Let k, r, t be integers with k≥2, r≥3 and t≥2. If G is a K1,r-free graph of order at least (k−1)(t(r−1)+1)+1 with δ(G)≥t, then G contains k disjoint K1,ts.•The bound on |V(G)| is best possible if the conjecture is true. The conjecture has been confirmed in the following cases: t=2 (Fujita), r=t=3 (Fujita), r≥4 and t=3 (Jiang et al.), r≥2t−1 and t≥3 (Jiang et al.). Moreover Jiang, Chiba, Fujita and Yan gave a counterexample with |V(G)|=10k−10 for the conjecture when r=3,t=4, and they whether G contain k disjoint copies of K1,4 if G is a claw-free graph of order |V(G)|≥10k−9 with δ(G)≥4.•In this paper, we answer this question by proving the following theorem. Theorem. Let k be an integer with k≥2. If G is a claw-free graph of order at least 10k−9 with δ(G)≥4, then G contains k disjoint K1,4s.