Covering Planar Graphs with Forests, one Having Bounded Maximum Degree

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We prove that every planar graph has an edge partition into three forests, one having maximum degree at most 4. This answers a conjecture of Balogh et al. (J. Combin. Theory B. 94 (2005) 147-158). We also prove that every planar graph with girth g > 5 (resp. g > 6) has an edge partition into two forests, one having maximum degree 4 (resp. 2).
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2009, 99 (2), pp.314-322. 〈10.1016/j.jctb.2008.07.004〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00338319
Contributeur : Daniel Gonçalves <>
Soumis le : mercredi 12 novembre 2008 - 16:50:18
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Daniel Gonçalves. Covering Planar Graphs with Forests, one Having Bounded Maximum Degree. Journal of Combinatorial Theory, Series B, Elsevier, 2009, 99 (2), pp.314-322. 〈10.1016/j.jctb.2008.07.004〉. 〈lirmm-00338319〉

Partager

Métriques

Consultations de la notice

56