An Alternative Proof of the $H$-Factor Theorem

Abstract

Let $H:V(G)\to 2^{\mathbb{N}}$ be a set mapping for a graph $G$. Given a spanning subgraph $F$ of $G$, $F$ is called a {\it general factor} or an $H$-{\it factor} of $G$ if $d_F(x)\in H(x)$ for every vertex $x\in V(G)$. $H$-factor problems are, in general, $NP$-complete problems and imply many well-known factor problems (e.g., perfect matchings, $f$-factor problems and $(g,f)$-factor problems) as special cases. Lovász [The factorization of graphs (II), Acta Math. Hungar., 23 (1972), 223--246] gave a structure description and obtained a deficiency formula for $H$-optimal subgraphs. In this note, we use a generalized alternating path method to give a structural characterization and provide an alternative and shorter proof of Lovász's deficiency formula.