Maximum Colored Cuts in Edge‐Colored Complete Graphs
Huawen Ma · Journal of Mathematics · 2022
Max‐Cut problem is one of the classical problems in graph theory and has been widely studied in recent years. Maximum colored cut problem is a more general problem, which is to find a bipartition of a given edge‐colored graph maximizing the number of colors in edges going across the bipartition. In this work, we gave some lower bounds on maximum colored cuts in edge‐colored complete graphs containing no rainbow triangles or properly colored 4‐cycles.