The multicolour size-Ramsey number of powers of paths

Publication date 24 September 2020

Abstract: Given a positive integer

s

, a graph

G

is

s

-Ramsey for a graph

H

, denoted

G i g h t a r r o w (H)_{s}

, if every

s

-colouring of the edges of

G

contains a monochromatic copy of

H

. The

s

-colour size-Ramsey number

{h a t r}_{s} (H)

of a graph

H

is defined to be

{h a t r}_{s} (H) = m i n | E (G) | c o l o n G i g h t a r r o w (H)_{s}

. We prove that, for all positive integers

k

and

s

, we have

{h a t r}_{s} (P_{n}^{k}) = O (n)

, where

P_{n}^{k}

is the

k

th power of the

n

-vertex path

P_{n}

.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: The multicolour size-Ramsey number of powers of paths