Ramsey goodness and generalized stars

被引:26
作者
Lin, Qizhong [1 ]
Li, Yusheng [2 ]
Dong, Lin [2 ]
机构
[1] Fuzhou Univ, Dept Math, Fuzhou 350108, Peoples R China
[2] Tongji Univ, Dept Math, Shanghai 200092, Peoples R China
基金
中国国家自然科学基金;
关键词
NUMBERS;
D O I
10.1016/j.ejc.2009.10.011
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G and H be fixed graphs with s(G) = s (the minimum number of vertices in a color class over all proper vertex-colorings of G with x(G) colors). It is shown that r(K(1) + G, K(1) + nH) <= k(hn + s-1) + 1 for large n. where x(G) = k >= 2. In particular, ifs is odd or s is even and hn is odd, then r(K(1) + K(k)(s), K(1) + nH) = k(hn + s-1) + 1, where K(k)(s) is a complete k-partite graph with s vertices in each part, implying that K(1) + nH is not (K(1) + K(k)(s))-good. Moreover, r(K(1) + sK(2), K(1) + nH) = 2hn + 1 for large n. (C) 2010 Published by Elsevier Ltd
引用
收藏
页码:1228 / 1234
页数:7
相关论文
共 16 条
  • [1] [Anonymous], 2013, Modern graph theory
  • [2] BURR S, 1981, J LOND MATH SOC, V2, P405
  • [3] GENERALIZATIONS OF A RAMSEY-THEORETIC RESULT OF CHVATAL
    BURR, SA
    ERDOS, P
    [J]. JOURNAL OF GRAPH THEORY, 1983, 7 (01) : 39 - 51
  • [4] The Ramsey numbers of stars versus wheels
    Chen, YJ
    Zhang, YQ
    Zhang, KM
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (07) : 1067 - 1075
  • [5] Chvatal V, 1977, J GRAPH THEOR, V1, P93, DOI [10.1002/jgt.3190010118, DOI 10.1002/JGT.3190010118]
  • [6] Erdo P., 1968, Theory of Graphs, P77
  • [7] Erdo P., 1962, Publ. Math. Inst. Hungar. Acad. Sci., V7, P623
  • [8] Erdo P., 1966, THEORY GRAPHS, P117
  • [9] On book-complete graph Ramsey numbers
    Li, YS
    Rousseau, CC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 68 (01) : 36 - 44
  • [10] Li YS, 1996, J GRAPH THEOR, V23, P413, DOI 10.1002/(SICI)1097-0118(199612)23:4<413::AID-JGT10>3.0.CO