General factors of graphs

Consider a graph \(G=(N,E)\) and, for each node \(i\in N\), let \(B_ i\) be a subset of \(\{0,1,...,d_ G(i)\}\) where \(d_ G(i)\) denotes the degree of node i in G. The general factor problem asks whether there exists a subgraph of G, say \(H=(N,F)\) where \(F\subseteq E\), such that \(d_ H(i)\in B_ i\) for every \(i\in N\). This problem is NP-complete. A set \(B_ i\) is said to have a gap of length \(p\geq 1\) if there exists an integer \(k\in B_ i\) such that \(k+1,...,k+p\not\in B_ i\) and \(k+p+1\in B_ i\). Lovász conjectured that the general factor problem can be solved in polynomial time when, in each \(B_ 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.

Recommendations

Cites work

Cited in

(58)

This page was built for publication: General factors of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085185)