TOPICS
Search

Vertex Arboricity


The vertex arboricity of a graph G, 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 V(G) can be partitioned so that each subset induces a forest. Equivalently, it is the minimum number of colors in a vertex coloring of G such that each color class induces an acyclic subgraph. The notion was introduced by Chartrand et al. (1968). It is sometimes denoted rho(G) or va(G).

Since each induced forest is bipartite, any such partition into k induced forests yields a proper coloring of G with at most 2k colors, so

 chi(G)<=2va(G),
(1)

and therefore

 va(G)>=[(chi(G))/2].
(2)

In particular,

 va(K_n)=[n/2].
(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.


See also

Albertson-Berman Conjecture, Arboricity, Induced Forest, Linear Arboricity, Star Arboricity

Explore with Wolfram|Alpha

References

Bollobás, B. and Harary, F. "Point Arboricity Critical Graphs Exist." J. London Math. Soc. 12, 97-102, 1975. https://doi.org/10.1112/jlms/s2-12.1.97.Chartrand, G. and Kronk, H. V. "The Point-Arboricity of Planar Graphs." J. London Math. Soc. 44, 612-616, 1969.Chartrand, G.; Kronk, H. V.; and Wall, C. E. "The Point-Arboricity of a Graph." Israel J. Math. 6, 169-175, 1968. https://doi.org/10.1007/BF02760181.Hakimi, S. L. and Schmeichel, E. F. "A Note on the Vertex Arboricity of a Graph." SIAM J. Disc. Math. 2, 64-67, 1989.Merker, L.; Schneider, S.; and Ueckerdt, T. "Characterizing Fixed-Treewidth Planar Graphs." 10 Nov 2026. https://arxiv.org/abs/2611.14327v1.

Cite this as:

Weisstein, Eric W. "Vertex Arboricity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexArboricity.html

Subject classifications