Realising every colour distribution sequence with a Gallai colouring

Abstract: An edge colouring of

K_{n}

with

k

colours is a Gallai

k

-colouring if it does not contain any rainbow triangle. Gy'arf'as, P'alv"olgyi, Patk'os and Wales proved that there exists a number

g (k)

such that

n g e q g (k)

if and only if for any colour distribution sequence

(e_{1}, c d o t s, e_{k})

with

, there exist a Gallai

k

-colouring of

K_{n}

with

e_{i}

edges having colour

i

. They also showed that

O m e g a (k) = g (k) = O (k^{2})

and posed the problem of determining the exact order of magnitude of

g (k)

. Feffer, Fu and Yan improved both bounds significantly by proving

O m e g a (k^{1.5} / l o g k) = g (k) = O (k^{1.5})

. We resolve this problem by showing

g (k) = T h e t a (k^{1.5} / (l o g k)^{0.5})

.

This page was built for publication: Realising every colour distribution sequence with a Gallai colouring