Bounds for Gallai-Ramsey functions and numbers

Abstract: For two graphs

G, H

and a positive integer

k

, the emph{Gallai-Ramsey number}

o p e r a t o r n a m e {g r}_{k} (G, H)

is defined as the minimum number of vertices

n

such that any

k

-edge-coloring of

K_{n}

contains either a rainbow (all different colored) copy of

G

or a monochromatic copy of

H

. If

G

and

H

are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved

o p e r a t o r n a m e {g r}_{k} (K_{s}, K_{t}) l e q s^{4 k t}

. Alon et al. showed that

o p e r a t o r n a m e {g r}_{k} (K_{s}, K_{t}) l e q (2 s^{3} + 4 s^{2})^{k t}

. In this paper, we prove that

o p e r a t o r n a m e {g r}_{k} (K_{s}, K_{t}) l e q 2^{k t} s^{3 k t}

for

t g e q 47

. We also give better upper bounds for

o p e r a t o r n a m e {g r}_{k} (G, H)

when

G, H

are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lov'{a}sz Local Lemma.

This page was built for publication: Bounds for Gallai-Ramsey functions and numbers