TOPICS
Search

Vertex Arboricity

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The vertex arboricity of a graph G, also called the point-arboricity, 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, Kronk, and Wall (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.

See also

Arboricity, Linear Arboricity, Star Arboricity

Explore with Wolfram|Alpha

References

Chartrand, G.; Kronk, H. V.; and Wall, C. E. "The Point-Arboricity of a Graph." Israel J. Math. 6, 169-175, 1968.Chartrand, G. and Kronk, H. V. "The Point-Arboricity of Planar Graphs." J. London Math. Soc. 44, 612-616, 1969.Hakimi, S. L. and Schmeichel, E. F. "A Note on the Vertex Arboricity of a Graph." SIAM J. Disc. Math. 2, 64-67, 1989.

Cite this as:

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