Discussiones Mathematicae Graph Theory 24(2) (2004) 249-262
DOI: https://doi.org/10.7151/dmgt.1229
VERTEX-DISJOINT COPIES OF K4-
Ken-ichi Kawarabayashi
Department of Mathematics
Faculty of Science and Technology, Keio University
3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan
e-mail: k_keniti@comb.math.keio.ac.jp
Abstract
Let G be a graph of order n. Let Kl- be the graph obtained from Kl by removing one edge.In this paper, we propose the following conjecture:
Let G be a graph of order n ≥ lk with δ (G) ≥ (n-k+1)[(l-3)/(l-2)]+k-1. Then G has k vertex-disjoint Kl-.
This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem.
In this paper, we verify this conjecture for l=4.
Keywords: extremal graph theory, vertex disjoint copy, minimum degree.
2000 Mathematics Subject Classification: 05C70, 05C38.
References
[1] | N. Alon and R. Yuster, H-factor in dense graphs, J. Combin. Theory (B) 66 (1996) 269-282, doi: 10.1006/jctb.1996.0020. |
[2] | G.A. Dirac, On the maximal number of independent triangles in graphs, Abh. Math. Semin. Univ. Hamb. 26 (1963) 78-82, doi: 10.1007/BF02992869. |
[3] | Y. Egawa and K. Ota, Vertex-Disjoint K1,3 in graphs, Discrete Math. 197/198 (1999), 225-246. |
[4] | Y. Egawa and K. Ota, Vertex-disjoint paths in graphs, Ars Combinatoria 61 (2001) 23-31. |
[5] | Y. Egawa and K. Ota, K1,3-factors in graphs, preprint. |
[6] | A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Colloq. Math. Soc. János Bolyai 4 (1970) 601-623. |
[7] | K. Kawarabayashi, K4−-factor in a graph, J. Graph Theory 39 (2002) 111-128, doi: 10.1002/jgt.10007. |
[8] | K. Kawarabayashi, F-factor and vertex disjoint F in a graph, Ars Combinatoria 62 (2002) 183-187. |
[9] | J. Komlós, Tiling Túran theorems, Combinatorica 20 (2000) 203-218. |
Received 31 August 2002
Revised 6 February 2004
Close