On the vertex arboricity of planar graphs of diameter two (Q2384426)

The vertex arboricity of a graph \(G\) is the minimum number \(k\) such that there exists a \(k\)-partition \(V=V_1\cup\cdots\cup V_k\) of the vertex set \(V\) of \(G\) with the property that the induced subgraphs \(G(V_1),\dots,G(V_k)\) are forests. It is shown that the vertex arboricity of planar graphs of diameter 2 is at most 2. Main part of the proof is an analysis of the structure of maximal planar graphs of diameter 2. Furthermore, the authors show that the problem whether a graph of diameter 2 has vertex arboricity at most 2 is NP-complete.