Star-critical Ramsey numbers for cycles versus the complete graph on 5 vertices

Publication date: 15 January 2019

Abstract: Let

G

,

H

and

K

represent three graphs without loops or parallel edges and

n

represent an integer. Given any red blue coloring of the edges of

G

, we say that

K i g h t a r r o w (G, H)

, if there exists red copy of

G

in

K

or a blue copy of

H

in

K

. Let

K_{n}

represent a complete graph on

n

vertices,

C_{n}

a cycle on

n

vertices and

S_{n} = K_{1, n}

a star on

n + 1

vertices. The Ramsey number

r (G, H)

is defined as

m i n n m i d K_{n} i g h t a r r o w (G, H)

. Likewise, the star-critical Ramsey number

r_{*} (H, G)

is defined

m i n k m i d K_{r (G, H) - 1} s q c u p K_{1, k} i g h t a r r o w (H, G)

. When

n > 3

, in this paper we show that

r_{*} (C_{n}, K_{5}) = 3 n - 1

except

r_{*} (C_{4}, K_{5}) = 13

. We also characterize all Ramsey critical

r (C_{n}, K_{5})

graphs.

This page was built for publication: Star-critical Ramsey numbers for cycles versus the complete graph on 5 vertices