Reduction from a m-coloring to a m-partition

Question

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.

Answer 1

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.