# Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k - Download this document for free, or read online. Document in PDF available to download.

1 NSU - Institute of Mathematics, NSU - Russia 2 Research Institute of Mathematics of Yakut - Russia 3 LaBRI - Laboratoire Bordelais de Recherche en Informatique 4 ALGCO - Algorithmes, Graphes et Combinatoire LIRMM - Laboratoire d-Informatique de Robotique et de Microélectronique de Montpellier

Abstract : A graph $G$ is $k,0$-colorable if its vertices can be partitioned into subsets $V 1$ and $V 2$ such that in $GV 1$ every vertex has degree at most $k$, while $GV 2$ is edgeless. For every integer $k\ge 1$, we prove that every graph with the maximum average degree smaller than $\frac {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$.

Author: O.V. Borodin - A.O. Ivanova - Mickael Montassier - Pascal Ochem - André Raspaud -

Source: https://hal.archives-ouvertes.fr/