Generalized Ramsey numbers: forbidding paths with few colors

Abstract

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.

9 pages