Size Ramsey numbers of stars versus 3-chromatic graphs

Authors
Citation
O. Pikhurko, Size Ramsey numbers of stars versus 3-chromatic graphs, COMBINATORI, 21(3), 2001, pp. 403-412
Citations number
6
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
21
Issue
3
Year of publication
2001
Pages
403 - 412
Database
ISI
SICI code
0209-9683(2001)21:3<403:SRNOSV>2.0.ZU;2-W
Abstract
Let K-1,K-n be the star with n edges, K-3 be the triangle, and C-odd be the family of odd cycles. We establish the following bounds on the correspondi ng size Ramsey numbers. n(2) +(0.577 + o(1)) n(3/2) < (r) over cap (K-1,K-n, C-odd) less than or eq ual to (r) over cap (K-1,K-n, K-3) < n(2) + root 2n(3/2) + n. The upper (constructive) bound disproves a conjecture of Erdos. Also we show that (r) over cap (K-1,K-n, F-n)=(1+o(1))n(2) provided F-n is an odd cycle of length o(n) or Fn is a 3-chromatic graph of order o(log n).