Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete? 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,&amp;\text{if } \{v_i,v'\}\in E\\ 0,&amp;\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}&amp;...&amp;k_{n,v'_1}\\...&amp;...&amp;...\\ k_{1,v'_m}&amp;...&amp;k_{n,v'_m}} \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}^m
$$
Your bipartite graph describes a set system whose elements are the vertices in $V_1$ and whose sets are the vertices in $V_2$. Your condition is the same as asking whether the discrepancy is at most $1$.

If all sets have even size (i.e., all vertices in $V_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a given set system in which each set has even size has discrepancy zero. It turns out that this is NP-hard even if all sets have size 4. This problem is known as Max-2-2-Set-Splitting.

There are much stronger NP-hardness results on discrepancy, such as Tight hardness results for minimizing discrepancy by Charikar, Newman and Nikolov. You can find pointers on Max-2-2-Set-Splitting there.