Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree

François Dross 1 Mickaël Montassier 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : An $(I,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>\frac2{3 −M}−2$, if a graph has maximum average degree less than $M$, then it has an $(I,F_d)$-partition. Additionally, we prove that for all $\frac83 \le M < 3$ and $d>\frac1{3−M}$, if a graph has maximum average degree less than $M$ then it has an $(I,F_d)$-partition. It follows that planar graphs with girth at least $7$ (resp. $8$, $10$) admit an $(I,F_5)$-partition (resp. $(I,F_3)$-partition, $(I,F_2)$-partition).
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01730269
Contributor : Alexandre Pinlou <>
Submitted on : Friday, February 8, 2019 - 2:58:41 PM
Last modification on : Tuesday, February 12, 2019 - 9:27:54 AM
Long-term archiving on : Thursday, May 9, 2019 - 3:54:24 PM

File

6815-PDF file-23618-3-10-20180...
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01730269, version 1

Collections

Citation

François Dross, Mickaël Montassier, Alexandre Pinlou. Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree. The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (1), pp.#P1.45. ⟨http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45⟩. ⟨lirmm-01730269⟩

Share

Metrics

Record views

253

Files downloads

13