Independent transversals in bipartite correspondence-covers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912233839132672 |
|---|---|
| author | Cambie, Stijn Kang, Ross J. |
| author_facet | Cambie, Stijn Kang, Ross J. |
| contents | Suppose $G$ and $H$ are bipartite graphs and $L: V(G)\to 2^{V(H)}$ induces a partition of $V(H)$ such that the subgraph of $H$ induced between $L(v)$ and $L(v')$ is a matching whenever $vv'\in E(G)$. We show for each $\varepsilon>0$ that, if $H$ has maximum degree $D$ and $|L(v)| \ge (1+\varepsilon)D/\log D$ for all $v\in V(G)$, then $H$ admits an independent transversal with respect to $L$, provided $D$ is sufficiently large. This bound on the part sizes is asymptotically sharp up to a factor $2$. We also show some asymmetric variants of this result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_05428 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Independent transversals in bipartite correspondence-covers Cambie, Stijn Kang, Ross J. Combinatorics 05C15, 05C35, 05D05 Suppose $G$ and $H$ are bipartite graphs and $L: V(G)\to 2^{V(H)}$ induces a partition of $V(H)$ such that the subgraph of $H$ induced between $L(v)$ and $L(v')$ is a matching whenever $vv'\in E(G)$. We show for each $\varepsilon>0$ that, if $H$ has maximum degree $D$ and $|L(v)| \ge (1+\varepsilon)D/\log D$ for all $v\in V(G)$, then $H$ admits an independent transversal with respect to $L$, provided $D$ is sufficiently large. This bound on the part sizes is asymptotically sharp up to a factor $2$. We also show some asymmetric variants of this result. |
| title | Independent transversals in bipartite correspondence-covers |
| topic | Combinatorics 05C15, 05C35, 05D05 |
| url | https://arxiv.org/abs/2009.05428 |