Vertex arboricity of planar graphs without chordal 6-cycles

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].

Keywords:

• vertex arboricity
• planar graph
• cycle
• chord
• colouring

2000 AMS Subject Classification:

• 05C15

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.