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 Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2018

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

François Dross
Mickaël Montassier

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
250 Consultations
129 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More