On the Existence and Determination of Satisfactory Partitions in a Graph

摘要

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty sets V_1,V_2 such that for each vertex v, if v ∈ V_i then d_(V_i)(v) ≥ s(v), where s(v) ≤ d(v) is a given integer-valued function. This problem was introduced by Gerber and Kobler [EJOR 125 (2000), 283-291] for s = [d/2]. In this paper we study the complexity of this problem for different values of s.