Hongliang Lu ; Wei Wang ; Juan Yan - Antifactors of regular bipartite graphs

dmtcs:3233 - Discrete Mathematics & Theoretical Computer Science, June 4, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-16
Antifactors of regular bipartite graphsArticle

Authors: Hongliang Lu ; Wei Wang ; Juan Yan

    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ász 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éjols \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.


    Volume: vol. 22 no. 1
    Section: Graph Theory
    Published on: June 4, 2020
    Accepted on: May 9, 2020
    Submitted on: March 30, 2017
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 472 times.
    This article's PDF has been downloaded 257 times.