Let's say we have a bipartite graph $G=(V_1\dot\cup V_2,E)$.
We're now looking for a two-coloring (red/blue) of the vertices of $V_1$, so that for all vertices $v\in V_2$ the sum of edges coming from red vertices differs at most by 1 from the sum of edges coming from blue vertices.
In other words, we're looking for a two-coloring $c:V_1\to\{-1,1\}$ so that the following formula holds: $$ \forall v\in V_2:\left( \sum_{v'\in V_1\\\{v,v'\}\in E}c(v')\in \{-1,0,1\}\right) $$
My question: Is finding such a two-coloring (or showing that no such two-coloring exists) NP-complete?
There's a (somewhat) linear algebra formulation of this problem, though it doesn't seem to be very helpful:
Let $V_1 = \{v_1,...,v_n\}$. Then we can define for every vertex $v\in V_2$ the row vector $(k_{1,v},...,k_{n,v})$ with $$k_{i,v} =\begin{cases} 1,&\text{if } \{v_i,v'\}\in E\\ 0,&\text{else}\end{cases}$$.
If we now let $c_i\in \{-1,1\}$ be the color of vertex $v_i$, then the requirements for the two-coloring can be written as: $$ \forall v\in V_2:\qquad (k_{1,v},...,k_{n,v}) \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\} $$ or equivalently with $V_2 = \{v'_1,...,v'_m\}$: $$ \pmatrix{k_{1,v'_1}&...&k_{n,v'_1}\\...&...&...\\ k_{1,v'_m}&...&k_{n,v'_m}} \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}^m $$