A (5,5)-Colouring of K n with Few Colours

Source 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 ).