On the vertex partition of planar graphs into forests with bounded degree

Let G=(V,E) be a graph. A (Δd1,Δd2)-partition of a graph G is the partition of V(G) into two non-empty subsets V1 and V2, such that G[V1] and G[V2] are graphs with maximum degree at most d1 and d2, respectively. A similar definition can be given for the notation (Fd1,Fd2)-partition if G[V1] and G[V2...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2020-06, Vol.374, p.125032, Article 125032
Main Authors: Wang, Yang, Huang, Danjun, Finbow, Stephen
Format: Article
Language:English
Subjects:
Forest
Girth
Maximum degree
Vertex partition
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:Let G=(V,E) be a graph. A (Δd1,Δd2)-partition of a graph G is the partition of V(G) into two non-empty subsets V1 and V2, such that G[V1] and G[V2] are graphs with maximum degree at most d1 and d2, respectively. A similar definition can be given for the notation (Fd1,Fd2)-partition if G[V1] and G[V2] are forests with maximum degree at most d1 and d2, respectively. For any d1 and d2, Montassier and Ochem constructed graphs with girth 4 which do not admit (Δd1,Δd2)-partition. In this paper, we show that planar graphs with girth at least 5 and without adjacent 5-cycles admit (F3,F3)-partition.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2020.125032