Skip to main content
1 of 9

One part of a bipartite graph has max degree 3. Partition the other part to 3 equal subsets s.t. no vertex of the first part sees all the 3 subsets

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, almost no vertex in $V$ has neighbours from all the 3 color classes?

To quantify roughly and almost, one needs bounds that may depend on $|U|$, $|V|$ and $d$.