On the size-Ramsey number of cycles

Authors

Abstract: For given graphs

G_{1}, l d o t s, G_{k}

, the size-Ramsey number

h a t R (G_{1}, l d o t s, G_{k})

is the smallest integer

m

for which there exists a graph

H

on

m

edges such that in every

k

-edge coloring of

H

with colors

1, l d o t s, k

,

H

contains a monochromatic copy of

G_{i}

of color

i

for some

1 l e q i l e q k

. We denote

h a t R (G_{1}, l d o t s, G_{k})

by

h a t R_{k} (G)

when

G_{1} = c d o t s = G_{k} = G

. Haxell, Kohayakawa and L{}uczak showed that the size Ramsey number of a cycle

C_{n}

is linear in

n

i.e.

h a t R_{k} (C_{n}) l e q c_{k} n

for some constant

c_{k}

. Their proof, is based on the regularity lemma of Szemer'{e}di and so no specific constant

c_{k}

is known. In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We give an alternative proof of

h a t R_{k} (C_{n}) l e q c_{k} n

, avoiding the use of the regularity lemma. For two colours, we show that for sufficiently large

n

we have

h a t R (C_{n}, C_{n}) l e q 1 0^{6} i m e s c n,

where

c = 843

if

n

is even and

c = 113482

otherwise.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: On the size-Ramsey number of cycles