×

zbMATH — the first resource for mathematics

Decomposing graphs under degree constraints. (English) Zbl 0865.05058
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.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI