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

Danjun Huang, Wai Chee SHIU*, Weifan Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 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 languageEnglish
Pages (from-to)2304-2315
Number of pages12
JournalDiscrete Mathematics
Volume312
Issue number15
DOIs
Publication statusPublished - 6 Aug 2012

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Cycle
  • Planar graph
  • Vertex arboricity

Fingerprint

Dive into the research topics of 'On the vertex-arboricity of planar graphs without 7-cycles'. Together they form a unique fingerprint.

Cite this