A precise condition for independent transversals in bipartite covers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910335584174080 |
|---|---|
| author | Cambie, Stijn Haxell, Penny Kang, Ross J. Wdowinski, Ronen |
| author_facet | Cambie, Stijn Haxell, Penny Kang, Ross J. Wdowinski, Ronen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14778 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A precise condition for independent transversals in bipartite covers Cambie, Stijn Haxell, Penny Kang, Ross J. Wdowinski, Ronen Combinatorics Discrete Mathematics 05C69, 05D15, 05C15, 05C35 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. |
| title | A precise condition for independent transversals in bipartite covers |
| topic | Combinatorics Discrete Mathematics 05C69, 05D15, 05C15, 05C35 |
| url | https://arxiv.org/abs/2308.14778 |