How can I prove that these two graph coloring problems are polynomial time equivalent? 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)|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?
 A: It's interesting to notice that weighted improper $k$-coloring seems  $NP$-complete even for $\theta = 1, k = 2$; so unless $P=NP$ there is not a polynomial time reduction to $k$-coloring ($k = 2$); because $2$-coloring of graphs is in $P$.
A sketch of the reduction from NAE 3-SAT to unweighted $\theta=1$ improper 2-coloring of undirected graphs is the following [NOTE: I quickly made it for exercise, so it can be wrong or probably the result is already known].


*

*represent each variable $x_i$ with two $K_4$ gadgets, one node of the first $K_4$ represents $+x_i$, one node of the second $K_4$ represents $-x_i$; the nodes $+x_i$ and $-x_i$ are linked together and they cannot have the same color;

*represent each clause $Cj = (\ell_{j,1} \lor \ell_{j,2}  \lor \ell_{j,3})$ with a $K_3$ gadget; the three nodes $\ell_{j,1}, \ell_{j,2}, \ell_{j,3}$ of a clause gadget cannot have the same color; 

*if $\ell_{j,p} = x_i$ then add an edge between $\ell_{j,p}$ and $+x_i$; if $\ell_{j,p} = \neg x_i$ then add an edge between $\ell_{j,p}$ and $-x_i$.



It's not hard to prove that the resulting graph is 1-improper 2-colorable if and only if it exists an assignment of the $x_i$s such  that in each $C_j$ at least one literal is true and at least one literal is false (Not-All-Equal). 
The NP-completeness of weighted $\theta = 1$ improper 2-coloring of directed graphs follows from:


*

*weighted $\theta = 1$ improper 2-coloring of directed graphs is simply a generalization of unweighted $\theta = 1$ improper 2-coloring of directed graphs (build an NPC reduction setting weight = 1);

*$\theta = 1$ improper 2-coloring of directed graphs $\theta = 1$ improper 2-coloring of directed graphs is simply a generalization $\theta = 1$ improper 2-coloring of undirected graphs $\theta = 1$  (build an NPC reduction setting $w(u,v) = w(v,u)$)

A: Don't know how the simplest "manual" reduction would look like.
One possible approach is convert improper coloring to SAT
(say with a tool like CBMC) and then convert SAT to coloring.
This is polynomial.
