2023/09/11 by Wu, Zhuo, Yan, Jun
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.05606
An edge colouring of Kn with k colours is a Gallai k-colouring if it does not contain any rainbow triangle. Gyárfás, Pálvölgyi, Patkós and Wales proved that there exists a number g(k) such that n≥ g(k) if and only if for any colour distribution sequence (e1,⋯,ek) with ∑i=1kei=\binomn2, there exist a Gallai k-colouring of Kn with ei edges having colour i. They also showed that Ω(k)=g(k)=O(k2) and posed the problem of determining the exact order of magnitude of g(k). Feffer, Fu and Yan improved both bounds significantly by proving Ω(k1.5/log k)=g(k)=O(k1.5). We resolve this problem by showing g(k)=Θ(k1.5/(log k)0.5). Moreover, we generalise these definitions by considering rainbow H-free colourings of Kn for any general graph H, and the natural corresponding quantity g(H,k). We prove that g(H,k) is finite for every k if and only if H is not a forest, and determine the order of g(H,k) when H contains a subgraph with minimum degree at least 3.