An Alternative Proof of the H-Factor Theorem

2011/04/27 by Hongliang Lu, Lu, Hongliang, Qinglin Yu +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1104.5113

arxiv created 2011/04/27 · arxiv updated 2011/04/28

Abstract

Let H: V(G) → 2^ℕ be a set mapping for a graph G. Given a spanning subgraph F of G, F is called a \it general factor or an H-\it factor of G if d_F(x)∈ H(x) for every vertex x∈ V(G). H-factor problems are, in general, NP-complete problems and imply many well-known factor problems (e.g., perfect matchings, f-factor problems and (g, f)-factor problems) as special cases. Lovász [The factorization of graphs (II), Acta Math. Hungar., 23 (1972), 223--246] gave a structure description and obtained a deficiency formula for H-optimal subgraphs. In this note, we use a generalized alternating path method to give a structural characterization and provide an alternative and shorter proof of Lovász's deficiency formula.

Related

• On the Existence of General Factors in Regular Graphs
• On the Complexity of General Graph Factor Problems
• An Extension of Cui-Kano's Characterization Problem on Graph Factors
• Some sufficient conditions for path-factor uniform graphs
• Minimum Degree Threshold for H-factors with High Discrepancy