Geodesic
Antifactors of regular bipartite graphs
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1.

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

Let $G=(X,Y;E)$ be a bipartite graph, where $X$ and $Y$ are color classes and $E$ is the set of edges of $G$. Lov\'asz and Plummer \cite{LoPl86} asked whether one can decide in polynomial time that a given bipartite graph $G=(X,Y; E)$ admits a 1-anti-factor, that is subset $F$ of $E$ such that $d_F(v)=1$ for all $v\in X$ and $d_F(v)\neq 1$ for all $v\in Y$. Cornu\'ejols \cite{CHP} answered this question in the affirmative. Yu and Liu \cite{YL09} asked whether, for a given integer $k\geq 3$, every $k$-regular bipartite graph contains a 1-anti-factor. This paper answers this question in the affirmative.
DOI : 10.23638/DMTCS-22-1-16
Classification : 05C70 
@article{DMTCS_2020_22_1_a17,
     author = {Lu, Hongliang and Wang, Wei and Yan, Juan},
     title = {Antifactors of regular bipartite graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-16},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-16/}
}
TY  - JOUR
AU  - Lu, Hongliang
AU  - Wang, Wei
AU  - Yan, Juan
TI  - Antifactors of regular bipartite graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-16/
DO  - 10.23638/DMTCS-22-1-16
LA  - en
ID  - DMTCS_2020_22_1_a17
ER  - 
%0 Journal Article
%A Lu, Hongliang
%A Wang, Wei
%A Yan, Juan
%T Antifactors of regular bipartite graphs
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-16/
%R 10.23638/DMTCS-22-1-16
%G en
%F DMTCS_2020_22_1_a17
Lu, Hongliang; Wang, Wei; Yan, Juan. Antifactors of regular bipartite graphs. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi : 10.23638/DMTCS-22-1-16. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-16/

Cité par Sources :