Premium
Size ramsey numbers of stars versus 4‐chromatic graphs
Author(s) -
Pikhurko Oleg
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10086
Subject(s) - combinatorics , mathematics , ramsey's theorem , conjecture , graph , chromatic scale , stars , discrete mathematics , physics , astronomy
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