Degree-constrained 2-partitions of graphs (Q2419120)

Let \(\delta=\delta(H)\) denote a minimum degree of a vertex in a graph \(H\). A \((\delta\ge k_1, \delta\ge k_2)\)-partition of a graph \(G\) is a vertex-partition \((V_1, V_2)\) of \(G\) into two nonempty sets satisfying that \(\delta(G[V_i])\ge k_i\) for \(i = 1, 2\). There are multiple known results about the existence of \((\delta\ge k_1, \delta\ge k_2)\)-partitions. For instance, a result in [\textit{V. Chvátal}, J. Graph Theory 8, 51--53 (1984; Zbl 0536.05030)] implies that \((\delta\ge3, \delta\ge3)\)-partition is \(\mathcal{NP}\)-complete already for 4-regular graphs. The paper strenghtens known results and for all positive integers \(k_1\), \(k_2\) determines the complexity of deciding whether a given graph has a \((\delta\ge k_1, \delta\ge k_2)\)-partition (polynomial, if \(k_1+k_2\le 3\), \(\mathcal{NP}\)-complete otherwise). The authors also address the problem of finding a function \(g(k_1, k_2)\) such that the \((\delta\ge k_1, \delta\ge k_2)\)-partition problem is \(\mathcal{NP}\)-complete for the class of graphs of minimum degree less than \(g(k_1, k_2)\) and polynomial for all graphs with minimum degree at least \(g(k_1, k_2)\). They prove that \(g(1, k)\) exists and has value \(k\) for all \(k\ge 3\), that \(g(2, 2)\) also exists and has value 3 and that \(g(2, 3)\), if it exists, has value 4 or 5.