Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and a clique of order k − ℓ.
@article{bwmeta1.element.doi-10_7151_dmgt_1729,
author = {Tomoki Nakamigawa},
title = {A ramsey-type theorem for multiple disjoint copies of induced subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {249-261},
zbl = {1290.05110},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1729}
}
Tomoki Nakamigawa. A ramsey-type theorem for multiple disjoint copies of induced subgraphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 249-261. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1729/
[1] S.A. Burr, On the Ramsey numbers r(G, nH) and r(nG, nH) when n is large, Dis- crete Math. 65 (1987) 215-229. doi:10.1016/0012-365X(87)90053-7[Crossref] | Zbl 0621.05024
[2] S.A. Burr, On Ramsey numbers for large disjoint unions of graphs, Discrete Math. 70 (1988) 277-293. doi:10.1016/0012-365X(88)90004-0[Crossref][WoS] | Zbl 0647.05040
[3] S.A. Burr, P. Erd˝os and J.H. Spencer, Ramsey theorems for multiple copies of graphs, Trans. Amer. Math. Soc. 209 (1975) 87-99. doi:10.1090/S0002-9947-1975-0409255-0[Crossref] | Zbl 0273.05111
[4] R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory, 2nd Edition (Wi- ley, New York, 1990).
[5] T. Nakamigawa, Vertex disjoint equivalent subgraphs of order 3, J. Graph Theory 56 (2007) 159-166. doi:10.1002/jgt.20263[Crossref][WoS] | Zbl 1128.05028