Caterpillar arboricity of planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2007

Caterpillar arboricity of planar graphs


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 and versions

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



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 View
0 Download



Gmail Facebook X LinkedIn More