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

Danjun Huang; Wai Chee Shiu; Weifan Wang

doi:10.1016/j.disc.2012.03.035

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

Danjun Huang, Wai Chee Shiu^*, Weifan Wang

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

27 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	2304-2315
Number of pages	12
Journal	Discrete Mathematics
Volume	312
Issue number	15
DOIs	https://doi.org/10.1016/j.disc.2012.03.035
Publication status	Published - 6 Aug 2012

User-Defined Keywords

Cycle
Planar graph
Vertex arboricity

Access to Document

10.1016/j.disc.2012.03.035

Cite this

@article{ca8ac0ed14b0422c860cd10c3228db07,

title = "On the vertex-arboricity of planar graphs without 7-cycles",

abstract = "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.",

keywords = "Cycle, Planar graph, Vertex arboricity",

author = "Danjun Huang and Shiu, {Wai Chee} and Weifan Wang",

note = "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. ",

year = "2012",

month = aug,

day = "6",

doi = "10.1016/j.disc.2012.03.035",

language = "English",

volume = "312",

pages = "2304--2315",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "15",

}

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 - Journal article

AN - SCOPUS:84861621263

SN - 0012-365X

VL - 312

SP - 2304

EP - 2315

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 15

ER -

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

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this