Vertex partitions and maximum degenerate subgraphs

Let G be a graph with maximum degree d≥ 3 and ω(G)≤ d, where ω(G) is the clique number of the graph G. Let p₁ and p₂ be two positive integers such that d = p₁ + p₂. In this work, we prove that G has a vertex partition S₁, S₂ such that GS₁] is a maximum order (p₁‐1)‐degenerate subgraph of G and GS₂] is a (p₂‐1)‐degenerate subgraph, where GS_i] denotes the graph induced by the set S_i 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 p₁ and p₂ positive integers such that d = p₁ + p₂, the graph G has a partition S₁,S₂ such that for i = 1,2, Δ(GS_i])≤ p_i and GS_i] is (p_i‐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 S₁,S₂ such that S₁ is a maximum independent set and ω(GS₂])≤ d‐1; it also refines a result of Catlin and Lai 3 ]: every graph G of maximum degree d≥ 3 has a partition S₁,S₂ such that S₁ is a maximum size set with GS₁] acyclic and ω(GS₂])≤ d‐2. The cases d = 3, (d,p₁) = (4,1) and (d,p₁) = (4,2) were proved by Catlin and Lai 3 ]. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 227–232, 2007