A precise condition for independent transversals in bipartite covers
| Autor: | Cambie, Stijn, Haxell, Penny, Kang, Ross J., Wdowinski, Ronen |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\'o and Tardos. Comment: 10 pages, 2 figures; v2 is AAM accepted to SIDMA after incorporating minor corrections |
| Databáze: | arXiv |
| Externí odkaz: |
|