An explicit edge-coloring of K_n with six colors on every K₅

2017/04/04 by Cameron, Alex
#05C55 #05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1704.01156

Abstract

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ős and Gyárfás. It is also shown that f(n,5,6) = Ω(n^(1/2)).

Related

• A (5,5)-coloring of K_n with few colors
• A new variant of the Erdős-Gyárfás problem on K₅
• The Erdős-Gyárfás function f(n, 4, 5) = \frac 56 n + o(n) -- so Gyárfás was right
• A variant of the Erdős-Gyárfás problem for K₈
• Lower bounds on the Erdős-Gyárfás problem via color energy graphs