Maximum Colored Cuts in Edge-Colored Complete k-Partite Graphs and Complete Graphs

The Maximum Colored Cut problem aims to seek a bipartition of the vertex set of a graph, maximizing the number of colors in the crossing edges. It is a classical Max-Cut problem if the host graph is rainbow. Let mcc(G) denote the maximum number of colors in a cut of an edge-colored graph G. Let Ck be a cycle of length k; we say G is PC-Ck-free if G contains no properly colored Ck. We say G is a p-edge-colored graph if there exist p colors in G. In this paper, we first show that if G is a PC-C3-free p-edge-colored complete 4-partite graph, then mcc(G)=p. Let k≥3 be an integer. Then, we show that if G is a PC-C4-free p-edge-colored complete k-partite graph, then mcc(G)≥min{p−1,15p/16}. Finally, for a p-edge-colored complete graph G, we prove that mcc(G)≥p−1 if G is PC-C4-free, and mcc(G)≥min{p−6,7p/8} if G is PC-C5-free and p≥7.