Equitable vertex arboricity of planar graphs

2014/03/12 by Zhang, Xin
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1403.2810

Abstract

Let G₁ be a planar graph such that all cycles of length at most 4 are independent and let G₂ be a planar graph without 3-cycles and adjacent 4-cycles. It is proved that the set of vertices of G₁ and G₂ can be equitably partitioned into t subsets for every t≥ 3 so that each subset induces a forest. These results partially confirm a conjecture of Wu, Zhang and Li.

Related

• A conjecture on equitable vertex arboricity of graphs
• Partitioning planar graphs without 4-cycles and 6-cycles into a forest and a disjoint union of paths
• Partitioning triangle-free planar graphs into a forest and a linear forest
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• (I,F)-partition of planar graphs without cycles of length 4, 6, or 9