Geodesic
A Ramsey-type theorem for multiple disjoint copies of induced subgraphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 249-261

Voir la notice de l'article provenant de la source Library of Science

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 − ℓ.
Keywords: graph decomposition, induced subgraph, graph Ramsey theory, extremal graph theory 
Nakamigawa, Tomoki. A Ramsey-type theorem for multiple disjoint copies of induced subgraphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 249-261. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a3/
@article{DMGT_2014_34_2_a3,
     author = {Nakamigawa, Tomoki},
     title = {A {Ramsey-type} theorem for multiple disjoint copies of induced subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {249--261},
     year = {2014},
     volume = {34},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a3/}
}
TY  - JOUR
AU  - Nakamigawa, Tomoki
TI  - A Ramsey-type theorem for multiple disjoint copies of induced subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 249
EP  - 261
VL  - 34
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a3/
LA  - en
ID  - DMGT_2014_34_2_a3
ER  - 
%0 Journal Article
%A Nakamigawa, Tomoki
%T A Ramsey-type theorem for multiple disjoint copies of induced subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 249-261
%V 34
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a3/
%G en
%F DMGT_2014_34_2_a3

[1] S.A. Burr, On the Ramsey numbers r(G, nH) and r(nG, nH) when n is large, Discrete Math. 65 (1987) 215-229. doi:10.1016/0012-365X(87)90053-7

[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

[3] S.A. Burr, P. Erdős 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

[4] R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory, 2nd Edition (Wiley, 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