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


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

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