On the vertex-arboricity of planar graphs without 7-cycles

详细信息	查看全文 | 推荐本文 |

• 作者：Danjun Huang^a ; ^b ; ^{hdanjun@zjnu.cn} ; Wai Chee Shiu^c ; ^{wcshiu@hkbu.edu.hk} ; Weifan Wang^a ; ^wwf@zjnu.cn
• 关键词：Vertex arboricity ; Planar graph ; Cycle
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 August, 2012
• 卷：312
• 期：15
• 页码：2304-2315
• 文件大小：964 K

摘要

The vertex arboricity of a graph is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that for every planar graph . In this paper, we prove that if is a planar graph without 7-cycles. This extends a result in [A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064-1075] that for each , planar graphs without -cycles have .