Caterpillar arboricity of planar graphs |
| |
Authors: | D Gonçalves |
| |
Institution: | LaBRI, U.M.R. 5800, Université Bordeaux I, 351, cours de la Liberation, 33405 Talence Cedex, France |
| |
Abstract: | We solve a conjecture of Roditty, Shoham and Yuster P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the 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 (Ei)1?i?4 in such a way that GEi], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G. |
| |
Keywords: | Arboricity Caterpillar Planar graphs |
本文献已被 ScienceDirect 等数据库收录! |
|