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 [J].
BURR, SA ;
ERDOS, P .
JOURNAL OF GRAPH THEORY, 1983, 7 (01) :39-51
[4]   The Ramsey numbers of stars versus wheels [J].
Chen, YJ ;
Zhang, YQ ;
Zhang, KM .
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 [J].
Li, YS ;
Rousseau, CC .
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