Size Ramsey numbers of stars versus cliques

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 thatrˆ(K1,k,K3)≤2k+12−k2 and he conjectured...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2019-11, Vol.92 (3), p.275-286
Main Authors: Miralaei, M., Omidi, G.R., Shahsiah, M.
Format: Article
Language:English
Subjects:
Coloring
Graph theory
Ramsey number
restricted size Ramsey number
size Ramsey number
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 thatrˆ(K1,k,K3)≤2k+12−k2 and he conjectured that this upper bound on rˆ(K1,k,K3) is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows:rˆ(K1,k,Kn)={(k(n−1)+12)−(k2),k≥norkodd,(k(n−1)+12)−k(n−1)∕2otherwise. They proved the case k=2. In 2001, Pikhurko showed that this conjecture is not true for n=3 and k≥5, by 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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22453