Generalized Ramsey numbers: forbidding paths with few colors (Q2309212)

Summary: Let \(f(K_n, H, q)\) be the minimum number of colors needed to edge-color \(K_n\) 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(K_n, P_v, q)\) for almost all values of \(v\) and \(q\), where \(P_v\) is a path on \(v\) vertices.