Partitioning sparse graphs into an independent set and a forest of bounded degree

François Dross¹ ; Mickael Montassier² ; Alexandre Pinlou²

¹LIRMM Université de Montpellier
²LIRMM Université de Montpellier

The electronic journal of combinatorics, Tome 25 (2018) no. 1

Résumé

An $({\cal I},{\cal F}_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M<3$ and $d \ge \frac{2}{3-M} - 2$, if a graph has maximum average degree less than $M$, then it has an $({\cal I},{\cal F}_d)$-partition. Additionally, we prove that for all $\frac{8}{3} \le M < 3$ and $d \ge \frac{1}{3-M}$, if a graph has maximum average degree less than $M$ then it has an $({\cal I},{\cal F}_d)$-partition. It follows that planar graphs with girth at least $7$ (resp. $8$, $10$) admit an $({\cal I},{\cal F}_5)$-partition (resp. $({\cal I},{\cal F}_3)$-partition, $({\cal I},{\cal F}_2)$-partition).

Détail

DOI : 10.37236/6815

Classification : 05C10, 05C70, 05C15
Mots-clés : planar graphs, sparse graphs, vertex decompositions, independent sets, forests