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 
@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},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2014},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a3/
%G en
%F DMGT_2014_34_2_a3
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/