Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250121
Contributor : Daniel Gonçalves <>
Submitted on : Sunday, February 10, 2008 - 3:12:45 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

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⟩

Share

Metrics

Record views

383