In this paper, we study the parameterized complexity of the problems of
partitioning the vertex set of a graph@into two parts V_A and V_B such
that V_A induces a graph with@degree at most a (resp., an a-regular
graph) and V_B induces a graph with@degree at most b (resp., a b-
regular graph). These two problems are called Upper-Degree-Bounded
Bipartition and Regular Bipartition respectively.
First, we prove that the two problems are NP-complete with any
nonnegative integers a and b except a=b=0. Second, we show the fixed-
parameter tractability of constrained versions of these two problems
with parameter k=|V_A| being the size of one part of the bipartition by
deriving some problem kernels for them.