2016/01/25 by Miralaei, Meysam, Omidi, Gholamreza, Shahsiah, Maryam
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1601.06599
The size Ramsey number r(G,H) of two graphs G and H is the smallest integer m such that there exists a graph F on m edges with the property that every red-blue colouring of the edges of F , yields a red copy of G or a blue copy of H . In 1981 , Erdős observed that r(K1,k,K3)≤ \binom2k+12-\binomk2 and he conjectured that the corresponding upper bound on r(K1,k,K3) is sharp. In 1983 , Faudree and Sheehan extended this conjecture as follows: r(K1,k,Kn)= \ lr \binomk(n-1)+12-\binomk2 & ~k≥ n~ or~ k~ odd. \binomk(n-1)+12-k(n-1)/2 & otherwise. . They proved the case k=2 . In 2001 , Pikhurko showed that this conjecture is not true for n=3 and k≥ 5 , disproving the mentioned conjecture of Erdős. Here we prove Faudree and Sheehan's conjecture for a given k≥ 2 and n≥ k3+2k2+2k .