Vertex-disjoint copies of in -free graphs

详细信息    查看全文

• 作者：Suyun Jiang^a ; ^{jiang.suyun@163.com} ; Shuya Chiba^b ; ^{schiba@kumamoto-u.ac.jp} ; Shinya Fujita^c ; ^{fujita@yokohama-cu.ac.jp} ; Jin Yan^a ; ^{yanj@sdu.edu.cn}
• 关键词：05C70
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：649-654
• 全文大小：505 K
• 卷排序：340

文摘

A graph GG is said to be K1,rK1,r-free if GG does not contain an induced subgraph isomorphic to K1,rK1,r. Let k,r,tk,r,t be integers with k≥2k≥2 and t≥3t≥3. In this paper, we prove that if GG is a K1,rK1,r-free graph of order at least (k−1)(t(r−1)+1)+1(k−1)(t(r−1)+1)+1 with δ(G)≥tδ(G)≥t and r≥2t−1r≥2t−1, then GG contains kk vertex-disjoint copies of K1,tK1,t. This result shows that the conjecture in Fujita (2008) is true for r≥2t−1r≥2t−1 and t≥3t≥3. Furthermore, we obtain a weaker version of Fujita’s conjecture, that is, if GG is a K1,rK1,r-free graph of order at least (k−1)(t(r−1)+1+(t−1)(t−2))+1(k−1)(t(r−1)+1+(t−1)(t−2))+1 with δ(G)≥tδ(G)≥t and r≥6r≥6, then GG contains kk vertex-disjoint copies of K1,tK1,t.