Let $G:=(U, V, E)$ be a bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d ~ 20000$, 
and $\beta<<1 /3$.

**Motivation**-  The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you have instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most 7400 clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in V$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided. 

In the third paragraph each color class corresponds to a block of variables. Therefore, size of color classed should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks. Therefore we need $\beta <<1 /3$. 

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.