Let $d \gg 1$. Let $G:=(U, V, E)$ be some 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 \sim 20000$, 
and $\beta \ll 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 make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most $20000/3$ 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, the size of each color class 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 by at most $\beta n$. Therefore we need $\beta \ll 1 /3$. 


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



One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets
Let $G=(U,V,E)$ be a bipartite graph where $U=[n], V=\binom{[n]}{3}$, and there is an edge between $u \in U$ and $v \in V$ if and only if $u \in v$. Then $\deg(u)=\binom{n-1}{2}$ for all $u \in V$ and $\deg(v)=3$ for all $v \in V$. However, every colouring of $U$ with $3$ colours, such that each colour class has size roughly $\frac{n}{3}$ has about $\frac{n^3}{27}$ vertices in $V$ with neighbours from all three colour classes. This is about a $\frac{2}{9}$ fraction of all the vertices in $V$. 


I do not think that a $\frac{2}{9}$ fraction can be considered almost none for any reasonable definition of almost none, so this is probably impossible. 


