A Note on the Vertex Arboricity of a Graph
S. L. Hakimi, Edward F. Schmeichel · SIAM Journal on Discrete Mathematics · 1989
The vertex arboricity$a(G)$ of a graph G is the minimum number of subsets into which the vertices of G can be partitioned so that each subset induces an acyclic graph. A characterization of planar graphs G is given for which $a(G) = 2$, thereby answering a question of Grünbaum [Israel J. Math., 14 (1973), pp. 390–408]. The characterization is in terms of the dual graph $G^* $. As a corollary, a theorem of Stein that characterizes maximal planar graphs G with $a(G) = 2$ is obtained. This latter result implies that determining whether $a(G)\leqq 2$ is NP-complete for maximal planar graphs G.