Caterpillar arboricity of planar graphs
A caterpillar is a tree such that removing all the end vertices gives a path. The caterpillar arboricity of a graph is the smallest number of forests needed to cover the edge set of the graph so that each connected component of each forest is a caterpillar. The author shows that every planar graph has caterpillar arboricity at most four. This solves a problem posed by \textit{Y. Roditty}, \textit{B. Shoham} and \textit{R. Yuster} [Discrete Math. 226, No. 1--3, 411--417 (2001; Zbl 0961.05040)]. The present author also gives a linear-time algorithm which, for a given planar graph, constructs four forests of caterpillars covering the edge set of that graph.
- Decomposition of Finite Graphs Into Forests
- Efficient Planarity Testing
- scientific article; zbMATH DE number 1185295 (Why is no real title available?)
- Monotone paths in edge-ordered sparse graphs
- On acyclic colorings of planar graphs
- Research problems
- Star arboricity of graphs
- The interval number of a planar graph: Three intervals suffice
- Covering planar graphs with forests, one having bounded maximum degree
- On star and caterpillar arboricity
- Graphs with only caterpillars as spanning trees
- Trees, paths, stars, caterpillars and spiders
- On caterpillar factors in graphs
- The interval number of a planar graph is at most three
- Planar Ramsey graphs
- Edge-intersection graphs of grid paths: the bend-number
- The Graph Structure of the Generalized Discrete Arnold's Cat Map
- Trees, Paths, Stars, Caterpillars and Spiders
- Arbitrarily vertex decomposable caterpillars with four or five leaves
- scientific article; zbMATH DE number 1155352 (Why is no real title available?)
- Rollercoasters and caterpillars
- The Local Queue Number of Graphs with Bounded Treewidth
- A new sum of graphs and caterpillar trees
- Maximal independent sets in a generalisation of caterpillar graph
- Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
- Covering planar graphs with forests, one having a bounded maximum degree
- Most edge-orderings of \(K_{n}\) have maximal altitude
- The caterpillar-packing polytope
- On interval representations of graphs
- The Treewidth and Pathwidth of Graph Unions
- Three ways to cover a graph
This page was built for publication: Caterpillar arboricity of planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370451)
