Minimal colorings for properly colored subgraphs in complete graphs

Abstract

Let $pr(K_n,G)$ be the maximum number of colors in an edge-coloring of $K_n$ with no properly colored copy of $G$. In this paper, we show that $pr(K_n,G)-ex(n,{\mathcal{G}}^{\prime })=o(n^2),$ where ${\mathcal{G}}^{\prime }=\{G-M:M\text{ is a matching of }G\}$. Furthermore, we determine the value of $pr(K_n,P_l)$ for $l\ge 27$ and $n\ge 2l^3$ and the exact value of $pr(K_n,G)$, where $G$ is $C_5,C_6$ and $K_4^{-}$, respectively. Also, we give an upper bound and a lower bound of $pr(K_n,K_{2,3})$.

17 pages