### Vertex partitions and maximum degenerate subgraphs

### 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.

### Más información

Título según WOS: | Vertex partitions and maximum degenerate subgraphs |

Título según SCOPUS: | Vertex partitions and maximum degenerate subgraphs |

Título de la Revista: | JOURNAL OF GRAPH THEORY |

Volumen: | 55 |

Número: | 3 |

Editorial: | Wiley |

Fecha de publicación: | 2007 |

Página de inicio: | 227 |

Página final: | 232 |

Idioma: | English |

URL: | http://doi.wiley.com/10.1002/jgt.20235 |

DOI: |
10.1002/jgt.20235 |

Notas: | ISI, SCOPUS |