Abstract For an edge-colored graph, the Maximum Colored Cut problem is to find a bipartition maximizing the number of colors in edges going across the bipartition. This problem is a generalization of the classical Max-Cut problem. Let G be an edge-colored graph with p colors, and let mcc (G) be the maximum number of colors in a cut of G. In this work, we show that (1) if G is a complete graph containing no properly colored K 4 − K₄^- s, where K 4 − K₄^- is the graph obtained from the complete graph on four vertices by deleting an edge, then mcc (G) ≥ 2 p /3; (2) if G is a complete k -partitie graph (k ≥ 3) containing no properly colored four-cycles, then mcc (G) ≥ p − 1.
Ma Huawen (Thu,) studied this question.