A precise condition for independent transversals in bipartite covers

Stijn Cambie; Penny Haxell; Ross J. Kang; Ronen Wdowinski

paper

A precise condition for independent transversals in bipartite covers

arXiv:2308.14778

Abstract

Given a bipartite graph $H = (V = V_{A} \cup V_{B}, E)$ in which any vertex in $V_{A}$ (resp.~ $V_{B}$ ) has degree at most $D_{A}$ (resp.~ $D_{B}$ ), suppose there is a partition of $V$ that is a refinement of the bipartition $V_{A} \cup V_{B}$ such that the parts in $V_{A}$ (resp.~ $V_{B}$ ) have size at least $k_{A}$ (resp.~ $k_{B}$ ). We prove that the condition $D_{A} / k_{B} + D_{B} / k_{A} \leq 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.

10 pages, 2 figures; v2 is AAM accepted to SIDMA after incorporating minor corrections