A (5,5)-Colouring of Kn with Few Colours
2018
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 Gyarfas, and comes close to matching the best known lower bound Ω( n 1/3 ).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
2
Citations
NaN
KQI