The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers

被引：0

作者：

Yusheng Li

Wenan Zang

机构：

[1] Tongji University,Department of Mathematics

来源：

Journal of Combinatorial Optimization | 2003年 / 7卷

关键词：

independence number; Ramsey number; probabilistic method; graph coloring;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let k ≥ 5 be a fixed integer and let m = ⌊(k − 1)/2⌋. It is shown that the independence number of a Ck-free graph is at least c1[∑ d(v)1/(m − 1)](m − 1)/m and that, for odd k, the Ramsey number r(Ck, Kn) is at most c2(nm + 1/log n)1/m, where c1 = c1(m) > 0 and c2 = c2(m) > 0.

引用

页码：353 / 359

页数：6

共 27 条

[1]

Ajtai M.(1980)A note on Ramsey numbers J. Combin. Theory Ser. A 29 354-360

[2]

Komlós J.(1973)Ramsey numbers for cycles in graphs J. Combin. Theory Ser. B 14 46-54

[3]

Szemerédi E.(2000)Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers Discrete Math. 220 51-56

[4]

Bondy J.A.(1978)On cycle-complete Ramsey numbers J. Graph Theory 2 53-64

[5]

Erdős P.(1959)Maximal paths and circuits in graphs Acta Math. Acad. Sci. Hungar. 10 337-356

[6]

Caro Y.(1983)An upper bound on the Ramsey number J. Combin. Theory Ser. A 35 145-152

[7]

Li Y.(1995)(3 Random Structure and Algorithms 7 173-207

[8]

Rousseau C.C.(1996)) J. Combin. Theory Ser. B 68 36-44

[9]

Zhang Y.(2001)The Ramsey number Graphs and Combin. 17 123-128

[10]

Erdős P.(2003)(3 J. Combin. Theory Ser. B 87 280-288

← 1 2 3 →