Abstract

Let G be a graph with maximum degree d ≥ 3 and ω(G) ≤ d, where ω(G) is the clique number of the graph G. Let P1 and p 2 be two positive integers such that d= P1 + p 2. In this work, we prove that G has a vertex partition {S 1,S2} such that G[S1] is a maximum order (P1 - 1)-degenerate subgraph of G and G[S2] is a (p 2 - 1)-degenerate subgraph, where G[Si] denotes the graph induced by the set Si- in G, for i = 1,2. On one hand, by using a degree-equilibrating process our result implies a result of Bollobas and Marvel [1]: for every graph G of maximum degree d ≥ 3 and ω(G) ≤ d, and for every p1 and p2 positive integers such that d = P 1 + p2, the graph G has a partition (S1, S 2] such that for i=1, 2, Δ(G[Si]) ≤ pi and G[Si] is (pi - 1)-degenerate. On the other hand, our result refines the following result of Catlin in [2]: every graph G of maximum degree d ≥ 3 has a partition [S1, S2] such that S 1 is a maximum independent set and ω(G[S2]) ≤ d- 1; it also refines a result of Catlin and Lai [3]: every graph G of maximum degree d ≥ 3 has a partition [S1, S2] such that S 1 is a maximum size set with G[S1] acyclic and ω(G[S2]) ≤ d-2. The cases d = 3, (d, P1) = (4, 1) and (d, P1) = (4, 2) were proved by Catlin and Lai [3]. © 2007 Wiley Periodicals, Inc.