Frontiers of Mathematics in China >
Disjoint in claw-free graphs with minimum degree at least five
Received date: 17 Mar 2012
Accepted date: 04 Oct 2014
Published date: 30 Dec 2014
Copyright
A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let be the graph obtained by removing exactly one edge from K4 and let k be an integer with . We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of . The requirement of number five is necessary.
Key words: Forbidden graph; vertex-disjoint subgraph; minimum degree
Yunshu GAO , Qingsong ZOU . Disjoint in claw-free graphs with minimum degree at least five[J]. Frontiers of Mathematics in China, 2015 , 10(1) : 53 -68 . DOI: 10.1007/s11464-014-0434-y
1 |
Bondy J A, Murty U S R. Graph Theory. 2nd ed. New York: Springer, 2008
|
2 |
Fujita S. Disjoint stars and forbidden subgraphs. Hiroshima Math J, 2006, 36: 397-403
|
3 |
Fujita S. Vertex-disjoint copies of K1+ (K1
|
4 |
Kawarabayashi K. F-factor and vertex-disjoint F in a graph. Ars Combin, 2002, 62: 183-187
|
5 |
Kawarabayashi K.
|
6 |
Wang H. Vertex-disjoint triangles in claw-free graphs with minimum degree at least three. Combinatorica, 1998, 18(3): 441-447
|
7 |
Zhang X, Li N, Wu J L, Yan J. Vertex-disjoint triangles in K1,t-free graphs with minimum degree at least t. Discrete Math, 2010, 310(19): 2499-2503
|
/
〈 | 〉 |