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).
Type de document :
Article dans une revue
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〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01730269
Contributeur : Alexandre Pinlou <>
Soumis le : vendredi 8 février 2019 - 14:58:41
Dernière modification le : mardi 12 février 2019 - 09:27:54

Fichier

6815-PDF file-23618-3-10-20180...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

8