A (5, 5)-Colouring of Kn with Few Colours. (9th May 2018)

• Record Type: Journal Article
• Authors: CAMERON, ALEX; HEATH, EMILY
• Is Part Of: Combinatorics, probability and computing. Volume 27:Number 6(2018)
• Page Start: 892
• Page End: 912
• Publication Date: 2018-05-09
• Subjects: Primary 05C55, -- Secondary 05C35, -- 05C25, -- 05D10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000172
• Languages: English
• ISSNs: 0963-5483

Abstract

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