2019/06/17 by Krueger, Robert A.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1906.06935
Let f(Kn, H, q) be the minimum number of colors needed to edge-color Kn so that every copy of H is colored with at least q colors. Originally posed by Erdős and Shelah when H is complete, the asymptotics of this extremal function have been extensively studied when H is a complete graph or a complete balanced bipartite graph. Here we investigate this function for some other H, and in particular we determine the asymptotic behavior of f(Kn, Pv, q) for almost all values of v and q, where Pv is a path on v vertices.