The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers |
| |
| Authors: | Yusheng Li Wenan Zang |
| |
| Affiliation: | (1) Department of Mathematics, Tongji University, Shanghai, 200092, China |
| |
| Abstract: | 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. |
| |
| Keywords: | independence number Ramsey number probabilistic method graph coloring |
| 本文献已被 SpringerLink 等数据库收录！ |
|
