Size ramsey numbers of stars versus 4‐chromatic graphs

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