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

• Autorzy: Tomoki Nakamigawa
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 2
• Strony: 249-261

Daty

wydano

2014-05-01

online

2014-04-12

Twórcy

autor

Tomoki Nakamigawa

• Department of Information Science Shonan Institute of Technology 1-1-25 Tsujido-Nishikaigan, Fujisawa Kanagawa 251-8511, Japan

Bibliografia

• [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]
• [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]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1729