1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 26 '20 at 20:49
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.