Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
A $\theta$-improper coloring of $G$ is a coloring where each node can have at most $\theta$ neighbors with the same coloring.
Now, given a weighted digraph $G(V,A,\omega)$ with weight function $\omega(u,v), (u,v)\in A$, a weighted $\theta$-improper $k$-coloring of $G$ is a coloring of the nodes such that for every node $v$:
$$ \sum_{u \in N(v)}\omega(u,v)\le \theta, $$$$ \sum_{u \in N(v)|c(u)=c(v)}\omega(u,v)\le \theta, $$
where $N(v)$ denotes the adjacent vertices of $v$, and $c(v)$ denotes the color of vertex $v$. Note that this definition generalizes $\theta$-improprer colorings (chose weights equal to 1), and standard colorings (…and chose $\theta=0)$. Let this problem be $P_2$.
It is fairly easy to prove that finding a weighted $\theta$-improper coloring is an $\mathcal{NP}$ complete problem by proving that $P_1\propto P_2$ (by choosing an appropriate weight function), but I am struggling to prove that $P_2 \propto P_1$ (this is necessarily true, since both problems are $\mathcal{NP}$ complete.
In other words, given a weighted digraph $G(V,A,\omega)$, how can one find a weighted $\theta$-improper $k$-coloring of $G$ with a procedure that solves the standard $k$-coloring problem?
