Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ 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 K¯ₗ. This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1229,
author = {Ken-ichi Kawarabayashi},
title = {Vertex-disjoint copies of K-4},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {249-262},
zbl = {1061.05073},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1229}
}
Ken-ichi Kawarabayashi. Vertex-disjoint copies of K¯₄. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 249-262. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1229/
[000] [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. | Zbl 0855.05085
[001] [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. | Zbl 0111.35901
[002] [3] Y. Egawa and K. Ota, Vertex-Disjoint in graphs, Discrete Math. 197/198 (1999), 225-246. | Zbl 0934.05077
[003] [4] Y. Egawa and K. Ota, Vertex-disjoint paths in graphs, Ars Combinatoria 61 (2001) 23-31.
[004] [5] Y. Egawa and K. Ota, -factors in graphs, preprint.
[005] [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. | Zbl 0217.02601
[006] [7] K. Kawarabayashi, K¯₄-factor in a graph, J. Graph Theory 39 (2002) 111-128, doi: 10.1002/jgt.10007. | Zbl 0992.05059
[007] [8] K. Kawarabayashi, F-factor and vertex disjoint F in a graph, Ars Combinatoria 62 (2002) 183-187. | Zbl 1073.05562
[008] [9] J. Komlós, Tiling Túran theorems, Combinatorica 20 (2000) 203-218. | Zbl 0949.05063