Grouping vertices in biregular graph Consider a $(a,b)$-biregular graph $(X,Y,E)$. In this case, $a|X|=b|Y|$ holds. Assume that $g:=|Y|/a=|X|/b$ is an integer. The goal is to find a subset $Y_0$ of $Y$ such that $|Y_0|=g$ and no two vertices in $Y_0$ have a common neighborhood, i.e., if $y_0,y_1\in Y_0$ then there is no $x\in X$ such that $(x,y_0),(x,y_1)\in E$. Is this grouping always possible?
Or, almost equivalently, is there a partition $\{X_i\}$ of $X$ with $|X_i|=g$ (so that $\bigcup_{i=1}^{b}X_i=X$) such that $|N(y)\cap X_i|=1$ for any $y\in Y$ and $i$, where $N(y)$ is the neighborhood of $y$?
 A: Here is a counterexample where one side cannot be partitioned as desired.  Curiously, in this example the other side can be partitioned as desired.  I don't know if there is a counterexample where neither side can be partitioned as desired.
Let $Y = [n] = \{1, 2, \dots, n\}$ and let $X = \{ (i, j) \in [n]^2: i < j \}$.  Further $(i,j) \in X$ connects to exactly $i, j \in Y$.  So every $x \in X$ has two neighbors and every $y \in Y$ has $n-1$ neighbors, and the graph is $(2, n-1)$-biregular.  Further, $|Y| = n$ and $|X| = n(n-1)/2$, so $g = |Y| / 2$ is an integer $\ge 2$ for even $n \ge 4$.
However, every pair of $y_0, y_1 \in Y$ shares the neighbor $(y_0, y_1) \in X$.  I.e. $Y$ cannot be partitioned as desired.
Curiously, it is possible to partition $X$.  E.g. for $n=4$ you can partition $X$ into three size-$g$ subsets as $\{(1,2),(3,4)\}, \{(1,3),(2,4)\}, \{(1,4), (2,3)\}$, and for each of the subsets (parts), the $x_0, x_1$ share no common $y \in Y$.  In fact, for this particular construction, $X$ can be partitioned into $n-1$ subsets of size $g=n/2$ each for any even $n \ge 4$ -- this is the edge coloring of the $n$-node complete graph for which there is a beautiful pictorial proof.

UPDATE 2020-05-06
In the above example, the larger side (i.e. $|X| = n(n-1)/2$) can be partitioned but the smaller side (i.e. $|Y| = n$) cannot.  The following is an example where the smaller side can be partitioned but the larger side cannot.
Simply generalize the above example by making $K$ copies of $Y$ and still use just one copy of $X$.  Each $y \in Y$ is still labeled with a number $j \in [n]$ and each $(i,j) \in X$ connects to every $i$ and every $j$ in $Y$.  Obviously, $Y$ still cannot be partitioned, since every two nodes in $Y$ share one neighbor (if they have different labels) or many neighbors (if they have equal labels).
Now, every $y \in Y$ still has $n-1$ neighbors but every $x \in X$ has $2K$ neighbors.  By making $K > (n-1)/2$, the un-partitionable side $Y$ (size $Kn$) is now the bigger side.  BTW $g = |Y|/2K = Kn/2K = n/2 = |X|/(n-1) $ as before (independent of $K$), and is still an integer $\ge 2$ for even $n \ge 4$.
