# A ramsey-type theorem for multiple disjoint copies of induced subgraphs

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 249-261
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTomoki Nakamigawa. "A ramsey-type theorem for multiple disjoint copies of induced subgraphs." Discussiones Mathematicae Graph Theory 34.2 (2014): 249-261. <http://eudml.org/doc/268005>.

@article{TomokiNakamigawa2014,

abstract = {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 − ℓ.},

author = {Tomoki Nakamigawa},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph decomposition; induced subgraph; graph Ramsey theory; extremal graph theory},

language = {eng},

number = {2},

pages = {249-261},

title = {A ramsey-type theorem for multiple disjoint copies of induced subgraphs},

url = {http://eudml.org/doc/268005},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Tomoki Nakamigawa

TI - A ramsey-type theorem for multiple disjoint copies of induced subgraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 2

SP - 249

EP - 261

AB - 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 − ℓ.

LA - eng

KW - graph decomposition; induced subgraph; graph Ramsey theory; extremal graph theory

UR - http://eudml.org/doc/268005

ER -

## References

top- [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] Zbl0621.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] Zbl0647.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] Zbl0273.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] Zbl1128.05028

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.