A precise condition for independent transversals in bipartite covers
share
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_A+D_B/k_B≤ 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 the other due to Szabó and Tardos.
READ FULL TEXT