Decomposing graphs under degree constraints. (English) Zbl 0865.05058

Stiebitz, Michael

J. Graph Theory 23, No. 3, 321-324 (1996).

A generalization of a conjecture of C. Thomassen is proved. The main result is formulated in the following theorem: Let \(G=(V,H)\) be a graph and \(a\), \(b\) two non-negative integer functions defined on \(V\). Assume that \(d_G(x)\geq a(x)+b(x)+1\) for every vertex \(x\) in \(V\). Then there exists a partition \((A,B)\) of \(V\) such that \(d_{G(A)}(x)\geq a(x)\) for every \(x\) in \(A\), and \(d_G(x)\geq b(x)\) for every \(x\) in \(B\). Thomassen’s conjecture is a straightforward consequence of this theorem.

Reviewer: L.Niepel (Bratislava)

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

degree constraints; decomposition; Thomassen’s conjecture