A conjecture on Gallai-Ramsey numbers of even cycles and paths

Publication date: 19 December 2019

Abstract: A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai

k

-coloring is a Gallai coloring that uses at most

k

colors. Given an integer

k g e 1

and graphs

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

, the Gallai-Ramsey number

G R (H_{1}, l d o t s, H_{k})

is the least integer

n

such that every Gallai

k

-coloring of the complete graph

K_{n}

contains a monochromatic copy of

H_{i}

in color

i

for some

i i n 1, 2, l d o t s, k

. When

H = H_{1} = c d o t s = H_{k}

, we simply write

G R_{k} (H)

. We study Gallai-Ramsey numbers of even cycles and paths. For all

n g e 3

and

k g e 2

, let

G_{i} = P_{2 i + 3}

be a path on

2 i + 3

vertices for all

i i n 0, 1, l d o t s, n - 2

and

G_{n - 1} i n C_{2 n}, P_{2 n + 1}

. Let

i_{j} i n 0, 1, l d o t s, n - 1

for all

j i n 1, 2, l d o t s, k

with

i_{1} g e i_{2} g e c d o t s g e i_{k}

. The first author recently conjectured that

G R (G_{i_{1}}, G_{i_{2}}, l d o t s, G_{i_{k}}) = | G_{i_{1}} | + s u m_{j = 2}^{k} i_{j}

. The truth of this conjecture implies that

G R_{k} (C_{2 n}) = G R_{k} (P_{2 n}) = (n - 1) k + n + 1

for all

n g e 3

and

k g e 1

, and

G R_{k} (P_{2 n + 1}) = (n - 1) k + n + 2

for all

n g e 1

and

k g e 1

. In this paper, we prove that the aforementioned conjecture holds for

n i n 3, 4

and all

k g e 2

. Our proof relies only on Gallai's result and the classical Ramsey numbers

R (H_{1}, H_{2})

, where

H_{1}, H_{2} i n C_{8}, C_{6}, P_{7}, P_{5}, P_{3}

. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: A conjecture on Gallai-Ramsey numbers of even cycles and paths