Size ramsey numbers of stars versus 4-chromatic graphs

✍ Scribed by Oleg Pikhurko

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 124 KB
• Volume: 42
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10086

✦ Synopsis

Abstract

We investigate the asymptotics of the size Ramsey number î(K~1,n~F), where K~1,n~ is the n‐star and F is a fixed graph. The author 11 has recently proved that r̂(K~1,n~,F)=(1+o(1))n^2^ for any F with chromatic number χ(F)=3. Here we show that r̂(K~1,n~,F)≤ ${\chi (F)(\chi(F)-2)}\over{2}$ n^2^+o(n^2^), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r̂(K~1,n~,F)=(4+o(1))n^2^ for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003