TY - JOUR
T1 - On the vertex-arboricity of planar graphs without 7-cycles
AU - Huang, Danjun
AU - SHIU, Wai Chee
AU - Wang, Weifan
N1 - Funding Information:
This work is supported partially by FRG, Hong Kong Baptist University, NSFC (No. 11071223 , No. 61170302 ), ZJNSF (No. Z6090150 ), ZSDZZZZXK08 and IP-OCNS-ZJNU.
PY - 2012/8/6
Y1 - 2012/8/6
N2 - The vertex arboricity va(G) of a graph G is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that va(G)≤3 for every planar graph G. In this paper, we prove that va(G)≤2 if G 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 k∈3,4,5,6, planar graphs G without k-cycles have va(G)≤2.
AB - The vertex arboricity va(G) of a graph G is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that va(G)≤3 for every planar graph G. In this paper, we prove that va(G)≤2 if G 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 k∈3,4,5,6, planar graphs G without k-cycles have va(G)≤2.
KW - Cycle
KW - Planar graph
KW - Vertex arboricity
UR - http://www.scopus.com/inward/record.url?scp=84861621263&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.03.035
DO - 10.1016/j.disc.2012.03.035
M3 - Article
AN - SCOPUS:84861621263
SN - 0012-365X
VL - 312
SP - 2304
EP - 2315
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 15
ER -