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

The full text of this article is unavailable through your IP address: 3.145.152.146

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