General factors of graphs

Reviewer: Robert P. J. Day

The author briefly describes the classical factor problem from graph theory and refers the reader to a polynomial solution for that problem. He then discusses the general factor problem originally introduced by Lova`sz [1,2]: For each node i ? N in some graph G = ( V,E), let B i be a subset of {0,1, . . . , deg( i)}. Does there exist F ? E such that, for each i ? N, the number of edges of F incident with i is an element of B i__?__ Some of Lova`sz's results involve the notion of gaps in the sets B i; the main result of this paper is a polynomial algorithm to decide whether a graph has a general factor when all sets B i have no gap of length larger than one. Section 2 of the paper describes the edge-and-triangle partitioning problem, for which a polynomial solution exists [3]; mentions a reduction due to Lova`sz from this problem to the bipartite 1-factor–antifactor problem; and then settles a question of Lova`sz by showing a polynomial time reduction for the converse. The remainder of the paper describes the polynomial solution to the general factor problem with no gaps of length greater than one. This solution reduces the original problem to a sequence of simpler factor problems. The author follows with a more direct algorithm.