PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 2 | 249-261
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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 − ℓ.
Wydawca
Rocznik
Tom
34
Numer
2
Strony
249-261
Opis fizyczny
Daty
wydano
2014-05-01
online
2014-04-12
Twórcy
  • Department of Information Science Shonan Institute of Technology 1-1-25 Tsujido-Nishikaigan, Fujisawa Kanagawa 251-8511, Japan, nakami@info.shonan-it.ac.jp
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1729
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.