Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
2 of 9
edited title

One part of a bipartite graph has max degree 3. Partition the other part to 3 equal subsets s.t. almost no vertex of the first part sees all 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$.