Maximum Colored Cuts in Edge-Colored Graphs Without Rainbow Short Cycles

A colored cut in an edge-colored graph [Formula: see text] is a bipartition of its vertex set and its size is the number of colors on edges between the two parts. The Maximum Colored Cut problem seeks to determine the maximum number of colors in colored cuts of [Formula: see text], denoted by [Formula: see text]. Say that [Formula: see text] is rainbow if no two edges of [Formula: see text] have the same color. This problem generalizes the classical Max-Cut problem when [Formula: see text] is rainbow. Let [Formula: see text] be a [Formula: see text]-edge-colored complete graph. In this paper, we show that if [Formula: see text] contains no rainbow triangles, then [Formula: see text]. The result holds for the edge-colored complete tripartite graphs without rainbow triangles as well. Moreover, we prove that if [Formula: see text] contains no rainbow [Formula: see text]-cycles, then [Formula: see text]. We also achieve the same bound if [Formula: see text] contains no rainbow subdivisions of either [Formula: see text] or [Formula: see text].