Size Ramsey numbers involving stars

✍ Scribed by R.J. Faudree; J. Sheehan

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 302 KB
• Volume: 46
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90248-0

✦ Synopsis

We calculate some size Ramsey numbers involving stars. For example we prove that for t ~ k w2 ~md n sufficiently large the size Ramsey number r,, (K,,k

All graphs in this paper are finite, simple and undirected. Let F, C and H be graphs. The number of vertices and edges of a graph F will be denoted by p(F) and q(F) resl~rctively, A graph F---~ (G, Hi if every 2-colouring (say red and blue) of the edges cf F produces either a 'red' G or a 'blue' H. Since all colourings of F below will be 2-colourings of the edges of F we shall simply refer to 'colouring~' of F. The Ramsey number r(G, ]~ = rp(G, H) = min{p(F3:F---~(G, H)}, the size Ramsey number rq( G, H) = min(q(F) : F'-+( G, H)}, and the restricted size Ramsey number

r*( G, H) = min{q( F) : F--) ( G, H), p( lO = r( G, H)}.

Also if H is a ,;ubgraph of G, then G-H will denote the graph obtained from G by deleting the edges of H. Thus both G and G-H will have the same vertex set. P denotes the complement of F. Suppose G and H ;.we distinct (disjoint) graphs. Then G U H is 'their disjoint union and G + H denotes the complement of t~ U/SL

The term 'size. Ramsey numbc~ was introduced in [5] and further studied in [4], [6], [8] and [9].

A survey of the few results concerning this function can be found it. [2]. The