A precise condition for independent transversals in bipartite covers
Preprint
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\le 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.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Degree criteria and stability for independent transversalsJournal of Graph Theory, 2024
- Asymmetric List Sizes in Bipartite GraphsAnnals of Combinatorics, 2021
- Bounded transversals in multipartite graphsJournal of Graph Theory, 2011
- Independent systems of representatives in weighted graphsCombinatorica, 2007
- Extremal Problems For Transversals In Graphs With Bounded DegreeCombinatorica, 2006
- A note on group coloringsJournal of Graph Theory, 2005
- A Note on Vertex List ColouringCombinatorics, Probability and Computing, 2001
- The choice number of random bipartite graphsAnnals of Combinatorics, 1998
- A condition for matchability in hypergraphsGraphs and Combinatorics, 1995
- On complete subgraphs of r-chromatic graphsDiscrete Mathematics, 1975