Vertex-disjoint triangles in K1,t-free graphs with minimum degree at least t

AbstractA graph is said to be K1,t-free if it does not contain an induced subgraph isomorphic to K1,t. Let h(t,k) be the smallest integer m such that every K1,t-free graph of order greater than m and with minimum degree at least t contains k vertex-disjoint triangles. In this paper, we obtain a lower bound of h(t,k) by a constructive method. According to the lower bound, we totally disprove the conjecture raised by Hong Wang [H. Wang, Vertex-disjoint triangles in claw-free graphs with minimum degree at least three, Combinatorica 18 (1998) 441–447]. We also obtain an upper bound of h(t,k) which is related to Ramsey numbers R(3,t). In particular, we prove that h(4,k)=9(k−1) and h(5,k)=14(k−1)