Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k |
| |
| Authors: | O V Borodin A O Ivanova M Montassier P Ochem A Raspaud |
| |
| Institution: | 1. Institute of Mathematics, Siberian Branch of Russian Academy and Novosibirsk State University, Novosibirsk 630090, Russia;2. Institute of Mathematics at Yakutsk State University, Yakutsk 677891, Russia;3. Université de Bordeaux—Labri UMR 5800, F‐33405 Talence Cedex, France;4. CNRS—LRI UMR 8623, BAT 490 Université Paris‐Sud 11, 91405 Orsay Cedex, France |
| |
| Abstract: | A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V1 and V2 such that in GV1] every vertex has degree at most k, while GV2] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+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 |
| |
| Keywords: | vertex decompositions sparse graphs |
|
|
