Vertex partitions and maximum degenerate subgraphs

✍ Scribed by Martín Matamala

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 109 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20235

✦ Synopsis

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