math.CO
Minimal colorings for properly colored subgraphs in complete graphs. 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' ) o(n 2 ), where mathcal G' 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 ) .