Abstract
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].
2000 AMS Subject Classification:
Acknowledgements
The work of Danjun Huang is supported by the Foundation of Zhejiang Educational Committee (Y201226078) and the work of Weifan Wang is supported by NSFC (No. 11071223), ZJNSF (No. Z6090150), ZJIP (No. T200905), ZSDZZZZXK13 and IP-OCNS-ZJNU.