Caterpillar arboricity of planar graphs

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 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2007, 307 (16), pp.2112-2121. 〈10.1016/j.disc.2005.12.055〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250121
Contributeur : Daniel Gonçalves <>
Soumis le : dimanche 10 février 2008 - 15:12:45
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Daniel Gonçalves. Caterpillar arboricity of planar graphs. Discrete Mathematics, Elsevier, 2007, 307 (16), pp.2112-2121. 〈10.1016/j.disc.2005.12.055〉. 〈lirmm-00250121〉

Partager

Métriques

Consultations de la notice

180