Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles The Electronic Journal of Combinatorics Year : 2018

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

François Dross
Mickaël Montassier

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).
Fichier principal
Vignette du fichier
6815-PDF file-23618-3-10-20180301.pdf (315.22 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01730269 , version 1 (08-02-2019)

Identifiers

Cite

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, 2018, 25 (1), pp.#P1.45. ⟨10.37236/6815⟩. ⟨lirmm-01730269⟩
252 View
132 Download

Altmetric

Share

More