A (5, 5)-Colouring of Kn with Few Colours. (9th May 2018) - CAMERON, ALEX; HEATH, EMILY
Abstract : For fixed integers p and q, let f ( n, p, q ) denote the minimum number of colours needed to colour all of the edges of the complete graph K n such that no clique of p vertices spans fewer than q distinct colours. Any edge-colouring with this property is known as a ( p, q )-colouring. We construct an explicit (5, 5)-colouring that shows that f ( n, 5, 5) ≤ n 1/3 + o (1) as n → ∞. This improves upon the best known probabilistic upper bound of O ( n 1/2 ) given by Erdős and Gyárfás, and comes close to matching the best known lower bound Ω( n 1/3 ).