On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs

Fang, Chunqiu and Győri, Ervin and Xiao, Jimeng (2021) On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs. GRAPHS AND COMBINATORICS, 37 (6). pp. 2287-2304. ISSN 0911-0119

Preview

Text s00373-021-02351-4.pdf - Published Version Available under License Creative Commons Attribution. Download (375kB) | Preview

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. For a family F of graphs, let e(x) (n, F) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in F as subgraphs. In this paper, we show that pr(K-n, G) - ex(n, G') = o(n(2)), where G' = {G - M : M is a matching of G}. Furthermore, we determine the value of pr(K-n, P-l) for sufficiently large n 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,K-3).

Actions (login required)

Edit Item