Vertex arboricity of planar graphs without chordal 6-cycles
Danjun Huang, Weifan Wang · International Journal of Computer Mathematics · 2012
The vertex arboricity va(G) of a graph G is the minimum number of colours the vertices can be coloured so that each colour class induces a forest. It was known that va(G)≤3 for every planar graph G, and the problem of computing vertex arboricity of graphs is NP-hard. In this paper, we prove that va(G)≤2 if G is a planar graph without chordal 6-cycles. This extends a result by Raspaud and Wang [On the vertex-arboricity of planar graphs, Eur. J. Combin. 29 (2008), pp. 1064–1075].