Vertex and tree arboricities of graphs
Journal
Journal of Combinatorial Optimization
Journal Volume
8
Journal Issue
3
Pages
295-306
Date Issued
2004
Author(s)
Abstract
This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.
SDGs
Type
journal article