The vertex arboricity of a graph , also called point-arboricity (Chartrand et al.
1968) or point arboricity (Bollobás and Harary 1975), is the minimum
number of subsets into which the vertex
set
can be partitioned so that each subset induces a forest.
Equivalently, it is the minimum number of colors in a
vertex coloring of
such that each color class induces an acyclic subgraph. The notion was introduced by Chartrand et
al. (1968). It is sometimes denoted
or
.
Since each induced forest is bipartite, any such partition into induced forests yields a
proper coloring of
with at most
colors, so
|
(1)
|
and therefore
|
(2)
|
In particular,
|
(3)
|
Chartrand and Kronk (1969) proved that every planar graph has vertex arboricity at most 3, and this bound is sharp.
Merker et al. (2026) proved that every finite simple graph that is planar and has treewidth at most 4 has vertex arboricity at most 2.