Contents Online

# 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

#### Authors

#### Abstract

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

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