✦ LIBER ✦
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
✍ Scribed by O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 127 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V~1~ and V~2~ such that in G[V~1~] every vertex has degree at most k, while G[V~2~] is edgeless. For every integer k⩾0, we prove that every graph with the maximum average degree smaller than (3__k__+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010