# Maximum Colored Cuts in Edge-Colored Complete Graphs

Authors: Huawen Ma
Journal: Journal of Mathematics
 (2022)

---

## Abstract

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.


---

## Body

## 1. Introduction

One of the classical partition problems is the well-known Max-Cut problem: given a graphG, find a partition V1,V2 of VG maximizing the number of edges going across V1 and V2. It has been a very active research subject in both combinatorics and computer science in the last 30 years. For a graph G, let fG be the maximum number of edges in a cut of G. For an integer m, let fm denote the minimum value of fG, as G ranges over all graphs with m edges. A simple probabilistic argument or a greedy algorithm shows that fm≥m/2. Answering a question of Erdos, Edwards [1, 2] in 1973 proved that(1)fm≥m/2+8m+1/8−1/8,and this is right as evidenced by complete graph with an odd number of vertices.In this work, we pay our attention to maximum colored cuts in edge-colored graphs: given a simple graphGV,E with an edge coloring c:E⟶1,2,…,p, and for each i∈p, c−1i≠∅, find a partition V1,V2 of VG maximizing the number of colors of edges going across V1 and V2. Faria et al. [3] proposed this problem and studied its complexity. Let m=EG. This problem converts to Max-Cut problem when p=m.For an edge-colored graphGV,E, we use Gi to denote the spanning subgraph of G induced by the edges of color i. We use colG to denote the set of colors appearing on EG. For each e∈EG, we also use cole to denote the color appearing on e. For any two disjoint subgraphs F and H of G, we use colF,H to denote the set of colors appearing on the edges between F and H. If VF=v, then we write colv,H instead of colF,H. For any two disjoint subsets S and T of VG, we use colS,T as shorthand for colGS,GT, where GS denote the subgraph of G induced by S. We say that G is properly colored if each pair of adjacent edges in G are assigned distinct colors. We say that G is monochromatic if colG=1. And we say that G is rainbow if all edges of G are assigned different colors. Let Kn be a complete graph with n vertices. A rainbow K3 is called a rainbow triangle. For a vertex v∈VG, the color degree of v, denoted by dGcv, is the number of different colors appearing on the edges incident with v.For an edge-colored graphG with p colors, let fcG be the maximum number of colors in a cut of G. Let fcp denote the minimum value of fcG, as G ranges over all edge-colored graphs with p colors. To distinguish from Max-Cut in graphs, we first need to forbid the following situation: p is close to m. If m−p=om, then fcp is close to fm. In addition, let G=Kn be an edge-colored complete graph with p=k2+1 colors such that a subgraph Kk is rainbow and the remaining edges are monochromatic. Then, it is easy to verify that fcG=fp−1+1 although p≪m. In these cases, we can give the lower bounds of the maximum colored cuts with the help of the results of the maximum cuts in graphs. To avoid these situations, we in this paper just discuss maximum colored cuts in edge-colored complete graphs, which contains no rainbow triangles or properly colored 4-cycles.Using the probabilistic approach, we first give a lower bound offcG by constraining mini∈pΔGi.Theorem 1.
LetGbe an edge-colored graph withcolG=p. For each colori∈p, ifΔGi≥k≥1, thenfcG≥1−1/2kp.The following four results discuss the lower bound offcG, as G is an edge-colored complete graph containing no rainbow triangles, properly colored 4-cycles, or monochromatic 4-cycles.Theorem 2.
LetGbe an edge-colored complete graph withcolG=p. IfGcontains no rainbow triangles or properly colored 4-cycles, thenfcG=p.Theorem 3.
LetGbe an edge-colored complete graph withcolG=p. IfGGcontains no properly colored 4-cycles, thenfcG≥3p/4.Theorem 4.
LetGbe an edge-colored complete graph withnvertices andpcolors. IfGcontains no rainbow triangles, then there is a constantδ>0, such thatfcG≥p/2+δp/2log2n.Theorem 5.
LetGbe an edge-colored complete graph withcolG=p. IfGcontains no rainbow triangles or monochromatic 4-cycles, thenfcG≥3p−1/4.
In the remainder of this paper, some useful lemmas are given in Section2, the proofs of Theorems 1–3 are given in Section 3, and the proofs of Theorem 4 and Theorem 5 are given in Section 4. Finally, we enumerate some open problems.


## 2. Preliminaries

We first state a useful lemma on the structure of edge-colored complete graphs containing no properly colored 4-cycle.Lemma 1 (see Martin et al. [4]).
LetGbe an edge-colored complete graph containing no properly colored 4-cycle. Then for each colori,Gi contains a dominating vertex.The following fundamental result on the existence of properly colored cycles in colored graphs plays a key role in our proofs.Lemma 2 (see Grossman and Häggkvist [5] and Yeo [6]).
LetGbe an edge-colored graph containing no properly colored cycles. ThenGcontains a vertexvsuch that no component ofG−vis joined tovwith edges of more than one color.
For an edge-colored graphG, a partition V1,V2,…,Vtt≥2 of VG is called a Gallai partition if ∪1≤i<j≤tcolVi,Vj≤2 and colVi,Vj=1 for 1≤i<j≤t.Lemma 3 (see Gallai [7]).
LetGbe an edge-coloredKn. IfGcontains no rainbow triangles, thenGhas a Gallai partition.
A graphG has vertices v1,v2,…,vn, let dvi be the degree of vi for 1≤i≤n. The sequence dv1,dv2,…,dvn is called a degree sequence of G. The following lemma, proved by Alon et al. [8], gives a lower bound of fG with respect to degree sequence of a sparse graph G.Lemma 4 (see Alon et al. [8]).
There exists an absolute constantε>0such that, for every constantC>0, there is a constantδ=δC>0with the following property. LetGbe a graph withnvertices,medges and degree sequencedv1,dv2,…,dvn. Suppose that the induced subgraph on any set ofd≥Cvertices all of which have a common neighbor contains at mostεd3/2edges. Then,(2)fG≥m2+δ∑i=1ndvi.


## 3. Proofs of Theorems 1–3

Proof of Theorem 1.
LetVG=V1∪V2 be a random partition of VG by placing each v∈VG into V1 or V2, independently, with probability 1/2. For each color i∈p, let Ii be the indicator random variable of the event that there exists an edge e=uv colored i such that u∈V1, v∈V2 or v∈V1, u∈V2. Recall that ΔGi≥k≥1. Then, there is a vertex v∈VG, which incidents with at least k edges-colored i. Let colV1,V2 denote the set of colors appearing on the edges between V1 and V2. Then,(3)Pri∈colV1,V2=EIi≥1−1/2k.
By the linearity of expectation,(4)EcolV1,V2=∑i∈pEIi≥1−1/2kp.
Thus, there exists a partitionVG=V1∪V2 such that colV1,V2≥1−1/2kp.Proof of Theorem 2.
LetG be an edge-colored complete graph containing no rainbow triangles or properly colored 4-cycles. Li et al [9] gave an observation, which shows that this graph G contains no properly colored cycles. For the sake of completeness, we recall the proof. By contradiction, suppose that C=v1v2,…,vtv1t≥5 is a properly colored cycle of minimal length in G. Without loss of generality, assume that colv1v2=1 and colv1vt=2, then colv3v4≠1. Since otherwise, C1=v1v4,…,vt−1vtv1 or C2=v1v2v3v4v1 would be a properly colored cycle shorter than C, a contradiction. Similarly, colv3v4≠2. Since otherwise, C3=v1v3,…,vt−1vtv1 or C4=v1v2v3v1 would be a properly colored cycle shorter than C, a contradiction too. Assume that colv3v4=3. Recall that C2=v1v2v3v4v1 is not a properly colored cycle. Hence, colv1v4=1 or 3. If colv1v4=3, then C1=v1v4,…,vt−1vtv1 would be a properly colored cycle, a contradiction, so colv1v4=1. Similarly, since C3=v1v3,…,vt−1vtv1 is not a properly colored cycle. Hence, colv1v3=2 or 3. If colv1v3=3, then C4=v1v2v3v1 would be a properly colored cycle, So colv1v3=2. Thus, v1v3v4v1 would be a properly colored cycle.
Note thatG contains no properly colored cycle. Then, by Lemma 2, there is a vn∈VG such that colvn,G1=G−vn=1. Note that G1 contains no properly colored cycle. There is a vn−1∈VG1 such that colvn−1,G2=G1−vn−1=1. Keep on doing this, we obtain a vertex sequence v1,v2,…,vn of VG and a graph sequence Gn,Gn−1,…,G1, such that colvi,Gn+1−i=1 for i∈n.
Now we placevn into V1 and place vn−1 into V2. Thus, colvn,G1⊆colV1,V2. Then, we place vn−2 into V1 and place vn−3 into V2, Thus, colvn−1,G2⊆colV1,V2 and colvn−2,G3⊆colV1,V2. The rest vertices can be placed in this way. Then, we have colvi,Gn+1−i⊆colV1,V2 for 1≤i≤n. Note that ∪1≤i≤ncolvi,Gn+1−i=colG=p. Hence, we can obtain a partition VG=V1∪V2 such that each edges colored fall into EV1,V2.Proof of Theorem 3.
LetG be an edge-colored complete graph containing no properly colored 4-cycle. We get the result easily if p≤2. So, we suppose that p≥3. If for each color i∈p, ΔGi≥2, then by Theorem 1, we have fcG≥3p/4. We are done. Now, we suppose that there exists a color j∈p such that Gj is a match. By Lemma 1, Gj contains a dominating vertex. So Gj is an edge. Assume that EGj=e=uv. If colu,v,VG\u,v=p−1, then we are done. So we suppose that colu,v,VG\u,v≤p−2, which implies that there is an edge in G\u,v, say f=u′v′, colored k and k∉colu,v,VG\u,v. Thus, uvv′u′u would be a properly colored 4-cycle, a contradiction.


## 4. Proofs of Theorems 4 and 5

Proof of Theorem 4.
LetG be an edge-colored Kn containing no rainbow triangles. By Lemma 3, G has a Gallai partition V11,V21,…,Vt1t≥2. Without loss of generality, suppose that V11≤n/2. Let GV1 be a subgraph of G induced by V1. Then, GV1 has a Gallai partition V12,V22,…,Vs2s≥2. Continuing this process, without loss of generality, we can get a V1l that V1l=1 and l≤log2n. Let V1l=vn. By the definition of Gallai partition, we have dGcvn≤2log2n. Let G1=G\vn. Then, there exists a vertex, say vn−1∈VG1, such that dG1cvn−1≤2log2n−1. Let G2=G1\vn−1. Similarly, there exists a vertex, say vn−2∈VG2, such that dG2cvn−2≤2log2n−2. Continuing this process, for each 1≤i≤n, there exists vi∈VGn−i such that dGn−icvi≤2log2i. We get a vertex sequence v1,v2,…,vn. Now we construct a rainbow subgraph G′ of G such that colG′=colG=p. Let G′G′ be a graph obtained from G by keeping one arbitrary edge from each color. Then, we have fcG≥fcG′=fG′. Note that G′G′ contains no triangles. Let d1,d2,…,dn be a degree sequence of G′. Let di+ denotes the number of neighbors vj of vi with j<i. Note that ∑i=1ndi+=p. Then,(5)∑i=1ndi≥∑i=1ndi+≥∑i=1ndi+2log2n=p2log2n.
By Lemma4, we complete the proof.Proof of Theorem 5.
LetG be an edge-colored complete graph containing no rainbow triangles and monochromatic 4-cycle. We claim that there is at most 1 color i∈p, such that ΔGi=1. Otherwise, let j,k∈p, such that ΔGj=1 and ΔGk=1. Let e=uv be colored j, and let f=xy be colored k. Obviously, e and f are not incident, as G contains no rainbow triangles, which implies that colu,v,x,y=1. Thus, uxvyu would be a monochromatic 4-cycle, a contradiction. So, there is at most 1 color in p that the edges colored and the color is a match. Let G′ be the subgraph of G by deleting the match. By Theorem 1, we have fcG≥fcG′≥3p−1/4.


## 5. Open Problems

In this section, we naturally proposed the following two problems on maximum colored cuts in edge-colored complete graphs.Problem 1.
What is the smallestcpsuch that each edge-colored complete graphGwithpcolors containing no rainbow triangles admits a partitionV1,V2satisfyingcolV1,V2≥cp?Problem 2.
What is the smallestcpsuch that each edge-colored complete graphGwithpcolors containing no properly colored 4-cycles admits a partitionV1,V2satisfyingcolV1,V2≥cp?



---

*Source: 9515498-2022-07-07.xml*