On the vertex arboricity of planar graphs of diameter two

An induced forest k-partition of a graph G is a k-partition ( V 1 , V 2 , … , V k ) of V ( G ) such that each G [ V i ] , 1 ⩽ i ⩽ k , is a forest. The vertex arboricity of a graph G is the minimum positive integer k for which G has an induced forest k-partition. In this paper, we show that the verte...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2007-09, Vol.307 (19), p.2438-2447
Main Authors: Aifeng, Yang, Jinjiang, Yuan
Format: Article
Language:English
Subjects:
Algebra
Arboricity
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Induced forest
Mathematics
Partition
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An induced forest k-partition of a graph G is a k-partition ( V 1 , V 2 , … , V k ) of V ( G ) such that each G [ V i ] , 1 ⩽ i ⩽ k , is a forest. The vertex arboricity of a graph G is the minimum positive integer k for which G has an induced forest k-partition. In this paper, we show that the vertex arboricity of planar graphs of diameter 2 is no more than two, and the induced forest 2-partition problem is NP-complete for graphs of diameter 2.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2006.10.017