# Reduction from a m-coloring to a m-partition

define a m-partition as: Given an undirected graph G = (V, E) and an integer j. Does there exist a partition of the vertices into m parts {V1, V2, ... , Vm} such that at least j of the edges have their endpoints in different parts of the partition?

I started by partitioning the graph into k parts: each partition represents 1 colouring of the graph. From there, I thought of reverting all edges: so converting all edges into non-edges and vice-versa. I'm stuck here. Am i on the right track? Thank you.

• Please do not delete questions once you have received an useful answer, we want these questions and answers to not only help you, but also others who have a similar problem. Instead, consider accepting an answer if it helped you. – Discrete lizard Apr 26 '20 at 20:49

By definition, a $$m$$-coloring is a function $$f : V \to \{1,\dots, m\}$$ such that $$\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$$. This means that at least $$|E|$$ edges have their endpoints in different sets of the partition $$\{V_1, \dots, V_m\}$$ of $$V$$ with $$V_i = \{ v \in V : f(v)=i \}$$.
On the contrary, if there is a partition $$\{V_1, \dots, V_m\}$$ of $$V$$ such that at least $$|E|$$ edges have their endpoints in different sets, then the function $$f : V \to \{1, \dots, k\}$$, where $$f(u)$$ is the unique index $$i_u \in \{1, \dots, m\}$$ such that $$u \in A_{i_u}$$, satisfies $$\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$$.
The above shows that the instance $$G=(V,E)$$ of $$m$$-coloring can be reduced (w.r.t. Karp reductions) to the instance $$\langle G, |E| \rangle$$ of $$m$$-partition.