Geodesic
Independent transversals in bipartite correspondence-covers
Canadian mathematical bulletin, Tome 65 (2022) no. 4, pp. 882-894

Voir la notice de l'article provenant de la source Cambridge

DOI

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.
DOI : 10.4153/S0008439521001004
Mots-clés : Graph coloring, bipartite graphs, independent transversals, correspondence coloring, Alon–Krivelevich conjecture 
Cambie, Stijn; Kang, Ross J. Independent transversals in bipartite correspondence-covers. Canadian mathematical bulletin, Tome 65 (2022) no. 4, pp. 882-894. doi: 10.4153/S0008439521001004
@article{10_4153_S0008439521001004,
     author = {Cambie, Stijn and Kang, Ross J.},
     title = {Independent transversals in bipartite correspondence-covers},
     journal = {Canadian mathematical bulletin},
     pages = {882--894},
     year = {2022},
     volume = {65},
     number = {4},
     doi = {10.4153/S0008439521001004},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439521001004/}
}
TY  - JOUR
AU  - Cambie, Stijn
AU  - Kang, Ross J.
TI  - Independent transversals in bipartite correspondence-covers
JO  - Canadian mathematical bulletin
PY  - 2022
SP  - 882
EP  - 894
VL  - 65
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439521001004/
DO  - 10.4153/S0008439521001004
ID  - 10_4153_S0008439521001004
ER  - 
%0 Journal Article
%A Cambie, Stijn
%A Kang, Ross J.
%T Independent transversals in bipartite correspondence-covers
%J Canadian mathematical bulletin
%D 2022
%P 882-894
%V 65
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439521001004/
%R 10.4153/S0008439521001004
%F 10_4153_S0008439521001004

Cité par Sources :