General Factors in Graphs.

Consider a graph GN,E and, for each node i is a member of N, let B sub I be a subset of 0,1,...,d sub Gi where d sub Gi denotes the degree of node i in G. The general factor problem asks whether there exists a subgraph of G, say HN,F where F is a subset of E, such that d sub Hi is a member of B sub i for every i belonging to N. This problem is NP-complete. A set B sub i is said to have a gap of length P or 1 if there exists an integer k is a member of B sub i such that k1,...,kp is not a member of B sub i and kp1 is a member of B sub i. Lovasz conjectured that the general factor problem can be solved in polynomial time when, in each B sub i, all the gaps if any have length one. We prove this conjecture. In cubic graphs, the result is obtained via a reduction to the edge-and-triangle partitioning problem. In general graphs, the proof uses an augmenting path theorem and an Edmonds-type algorithm.