# Upper bound for monochromatic edges in vertex coloring with k colors

I'm trying to find an upper bound of the number of monochromatic edges in a graph $$G=(V,E)$$, given k colors for Vertex coloring. An edge $$e=(u,v)\in E$$ is called monochromatic if both $$u$$ and $$v$$ have the same color.

If I understand right, for any $$k > 0$$, $$G$$ can be vertex k-colored so that at most $$\frac {|E|}{k}$$ of its edges are monochromatic. If it's true, how is it proved?

I'm assuming that by "vertex coloring" you are not referring to proper vertex coloring, since every proper vertex coloring has zero monochromatic edges.

I'll prove the claim using the Probabilistic method.

Given a graph $$G=(V,E)$$, and k colors, I'll define random coloring as a function $$C:V\to[k]$$ (where $$[k]:=\{1,2....,k\}$$) as follow: $$\forall v\in V, i\in[k]\ \ \ \ \mathbb {P}(c(v)=i)=\frac{1}{k}$$ Proposition $$\forall e\in E\ \ \ \mathbb {P}(e\text{ is monochromatic})=\frac{1}{k}$$ The proposition implies the expected number of monochromatic edges for such random coloring is $$\frac{\vert E\vert}{k}$$.

Therefore, at least one random coloring induce no more then $$\frac{\vert E\vert}{k}$$ monochromatic edges, otherwise, the expectation value would be higher.

The proposition proof is quite simple: $$\forall i\in [k],v,u\in V\ \ \ \ \mathbb P(c(u)=i\land c(v)=i) = \frac{1}{k^2}\implies\mathbb P(c(u)=c(v))=\frac{1}{k}$$ Where the last transition is true because there are k colors.

• You need to colour the vertices independently in order to conclude that the probability for matching colours is $\frac1{k^2}$. Dec 26, 2019 at 18:36
• You are correct! each vertex has equal probability to be color in each color, regardless of the other vertices coloring choice. Meaning vertices where color independently. Dec 26, 2019 at 18:59
• Thank you very much for your help! Dec 27, 2019 at 12:03
• Could it be that one color has atmost $\frac{|E|}{k}$ edges but an another color has > $\frac{|E|}{k}$ edges ? Nov 20, 2022 at 3:02
• @Balajisb The $\frac{|E|}{k}$ in this problem is a sum over all colors, not a separate quantity for each color. Nov 20, 2022 at 3:40