Independent transversals in bipartite correspondence-covers

Abstract

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^{\prime })$ is a matching whenever $v{v}^{\prime }\in E(G)$. We show for each $\epsilon >0$ that, if $H$ has maximum degree $D$ and $|L(v)|\ge (1+\epsilon )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.

14 pages; v2 added asymmetric version of Haxell's theorem, accepted to Canadian Mathematical Bulletin

References in corpus (3)

• Graph structure via local occupancy
• Colourings, transversals and local sparsity
• Asymmetric list sizes in bipartite graphs

Cited by in corpus (2)

• Packing list-colourings
• The $\chi$-Ramsey problem for triangle-free graphs