Disjoint Cliques in Claw-free Graphs  

作　　者：Su-yun JIANG Jin YAN 

机构地区：[1]School of Mathematics, Shandong University

出　　处：《Acta Mathematicae Applicatae Sinica》2018年第1期19-34,共16页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(Grant No.11271230,11671232)

摘　　要：A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n≥3 s ＋4（k-s） and d（x）＋ d（y）≥n-2 s ＋2 k ＋1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3 s and k-s disjoint K4 s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n≥3 s ＋4（k-s） and d（x）＋ d（y）≥n-2 s ＋2 k ＋1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3 s and k-s disjoint K4 s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.

关 键 词：claw-free graphs disjoint clique degree condition 

分 类 号：O1[理学—数学]