| Abstract | dc.description.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 p2 be two
positive integers such that d = p1 + p2. In this work, we prove that G has
a vertex partition {S1, S2} such that G[S1] is a maximum order (p1 − 1)-
degenerate subgraph of G and G[S2] is a (p2 − 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 =
p1 + p2, the graphG has a partition {S1, S2} such that for i = 1, 2,#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 S1 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 S1 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]. | en |
