Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

An alternative proof of general factor structure theorem

Pages: 2551 – 2568

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a10


Hongliang Lu (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China)

Qinglin Yu (Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, Canada)


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.


degree constrained factor, alternating path, changeable trail

2010 Mathematics Subject Classification


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