Caterpillar arboricity of planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2007

Caterpillar arboricity of planar graphs

Résumé

We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets that induce caterpillar forests. This positively answers a conjecture of Roditty, Shoham and Yuster (Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417) . We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.

Dates et versions

lirmm-00250121 , version 1 (10-02-2008)

Identifiants

Citer

Daniel Gonçalves. Caterpillar arboricity of planar graphs. Discrete Mathematics, 2007, 307 (16), pp.2112-2121. ⟨10.1016/j.disc.2005.12.055⟩. ⟨lirmm-00250121⟩
191 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More