An Explicit Edge-Coloring of $K_n$ with Six Colors on Every $K_5$
2019
For fixed integers p and q, let f(n,p,q) denote the minimum number of colors needed to color all of the edges of the complete graph K_n such that no clique of p vertices spans fewer than q distinct colors. A construction is given which shows that f(n,5,6) < n^(1/2+o(1)). This improves upon the best known probabilistic upper bound of O(n^(3/5)) given by Erd\H{o}s and Gy\'arf\'as. It is also shown that f(n,5,6) = {\Omega}(n^(1/2)).
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI