Some lower bounds for maximum colored cuts

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 <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <m:msubsup> <m:mrow> <m:mi>K</m:mi> </m:mrow> <m:mrow> <m:mn>4</m:mn> </m:mrow> <m:mrow> <m:mo>−</m:mo> </m:mrow> </m:msubsup> </m:math> K₄⁻ s, where <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <m:msubsup> <m:mrow> <m:mi>K</m:mi> </m:mrow> <m:mrow> <m:mn>4</m:mn> </m:mrow> <m:mrow> <m:mo>−</m:mo> </m:mrow> </m:msubsup> </m:math> 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.