A Precise Condition for Independent Transversals in Bipartite Covers

Given a bipartite graph H = (V = V_A \∪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 \∪ 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 \≤ 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\'o and Tardos.