An Alternative Proof of the H-Factor Theorem

MaRDI QIDQ6225044zbMATH OpenFDO

Authors Hongliang Lu, Qinglin Roger Yu

Publication date 27 April 2011

Abstract: Let $H:V(G)ightarrow{2}^{mathbbN}$ 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)inH(x)$ for every vertex $xinV(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'asz [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'asz's deficiency formula.

This page was built for publication: An Alternative Proof of the $H$-Factor Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6225044)