An Algorithm For Vertex - Partitioning Under Degree Constraints

Let s, t be two nonnegative integers, and g(s,t) be the minimum integer such that the vertex set of a graph G of minimum degree at least g(s,t) can be partitioned into two sets V1 and V2 which induced subgraphs of minimum degree at least s and t, respectively. Stiebitz proved that g(s,t)≤s+t+ 1, Kaneko and Diwan strengthened this result on some constraints of graphs, proving that it suffices to assume g(s, t)≤s+t (s, t≥1), or just g(s, t)≤ s+1 - 1 (s, t≥2) if G contains no cycle shorter than 4 or 5, respectively. Liu and Xu showed that g(s, t)≤s+1 (s, t≤1) on (K4-e)-free graphs except K3, and g(s, t)≤ s+t-1 (s, t≥2) on triangle-free graphs in which no two quadrilaterals share edges.Bazgan, Tuza and Vanderpooten gave polynomial-time algorithms that find such partitions under the results by Stiebitz, Kaneko and Diwan. In this the-sis, we give the polynomial-time algorithms that find such partitions under the results by Liu and Xu.