An alternative proof of general factor structure theorem

Let $G$ be a graph, and $H : V (G) \to 2^\mathbb{N}$ a set function associated with $G$. A spanning subgraph $F$ of graph $G$ is called a general factor or an $H$-factor of $G$ if $d_F (x) \in H(x)$ for every vertex $x \in V (G)$. The existence of $H$-factors is, in general, an $NP$-complete problem. $H$-factor problems are considered as one of most general factor problem because many well-studied factors (e.g., perfect matchings, $f$-factor problems and $(g,f)$-factor problems) are special cases of $H$-factors. Lovász [“The factorization of graphs (II),” Acta Math. Hungar., 23 (1972), 223–246] gave a structure description of $H$-optimal subgraphs and obtained a deficiency formula. In this paper, we introduce a new type of alternating path to study Lovász’s canonical structural partition of graphs and consequently obtain an alternative and shorter proof of Lovász’s deficiency formula for $H$-factors. Moreover, we also obtain new properties regarding Lovász’s canonical structural partition of $H$-factors.

Keywords

degree constrained factor, alternating path, changeable trail

2010 Mathematics Subject Classification

05C70

Full Text (PDF format)

This work is supported by the National Natural Science Foundation of China (No. 12271425), and Natural Sciences and Engineering Research Council of Canada (RGPIN-2019-06429).

Received 25 May 2021

Received revised 22 June 2022

Accepted 21 July 2022

Published 29 March 2023