Gallai-Ramsey numbers of C₁₀ and C₁₂

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

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, 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 continue to study Gallai-Ramsey numbers of even cycles and paths. For all

n g e 3

and

k g e 1

, 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, l d o t s, k

with

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

. Song recently conjectured that

G R (G_{i_{1}}, l d o t s, G_{i_{k}}) = 3 + m i n i_{1}, n^{*} - 2 + s u m_{j = 1}^{k} i_{j}

, where

n^{*} = n

when

G_{i_{1}} e P_{2 n + 1}

and

n^{*} = n + 1

when

G_{i_{1}} = P_{2 n + 1}

. This conjecture has been verified to be true for

n i n 3, 4

and all

k g e 1

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

n i n 5, 6

and all

k g e 1

. Our result implies that for all

k g e 1

,

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

for

n i n 5, 6

and

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

for

1 l e n l e 6

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Gallai-Ramsey numbers of \(C_{10}\) and \(C_{12}\)