Caterpillar arboricity of planar graphs
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.