zbMATH — the first resource for mathematics

Graph decomposition with constraint on the minimum degree. (English) Zbl 0625.05028
In [Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory 7, 165-167 (1983; Zbl 0515.05045)] the reviewer demonstrated the existence of a function g(s,t) such that every graph of minimum degree at least g(s,t) has two disjoint nonempty subgraphs which together cover all vertices of the graph and have minimum degree at least s and t, respectively. The main result of the present paper is the equality g(s,t)\(\leq s+2t-3\) for \(t\geq 4\). This was also proved by P. Hajnal [Combinatorica 3, 95-99 (1983; Zbl 0529.05030)].
Reviewer: C.Thomassen
05C35 Extremal problems in graph theory