.png){kind=icon}
.png){kind=icon}
Return
Some lower bounds for maximum colored cuts
.png){kind=icon}
PRE
AI
DOI：10.1515/math-2025-0229.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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}_{4}<<^>>{-}$ s, where K 4 - ${K}_{4}<<^>>{-}$ is the graph obtained from the complete graph on four vertices by deleting an edge, then mcc(G) >= 2p/3; (2) if G is a complete k-partitie graph (k >= 3) containing no properly colored four-cycles, then mcc(G) >= p - 1.
Keywords:
partition
maximum colored cut
edge-colored graph