Covering Planar Graphs with Forests, one Having Bounded Maximum Degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Theory, Series B Année : 2009

Covering Planar Graphs with Forests, one Having Bounded Maximum Degree

Résumé

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).

Dates et versions

lirmm-00338319 , version 1 (12-11-2008)

Identifiants

Citer

Daniel Gonçalves. Covering Planar Graphs with Forests, one Having Bounded Maximum Degree. Journal of Combinatorial Theory, Series B, 2009, 99 (2), pp.314-322. ⟨10.1016/j.jctb.2008.07.004⟩. ⟨lirmm-00338319⟩
92 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More