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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.