Antifactor of regular bipartite graphs

Hongliang Lu

Published 2015-11-30Version 1

This problem is NP-complete in general, but for the case when no prescription contains two consecutive gaps, Lov\'asz gave a structural description, and Cornu\'ejols gave a polynomial algorithm. However, results on $H$-factors are known only in some special cases, such as parity intervals or general antifactors. Let $k\geq 3$ be an integer. Let $G'$ be a $k$-regular bipartite graph with partition $(X,Y)$. In this paper, we show that $G'$ contains an $H$-factor, where $H(x)=\{1\}$ for all $x\in X$ and $H(y)=\{0,2,3,\ldots,k\}$ for all $y\in Y$, which solves a problem proposed by Liu and Yu.