2022/03/12 by Pongpat Sittitrai, Sittitrai, Pongpat, Kittikorn Nakprasit +1
Computer Science · #05C15 #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2203.06466
openalex publication_date 2022/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we show that every planar graph without 4-cycles and 6-cycles has a partition of its vertex set into two sets, where one set induces a forest, and the other induces a forest with maximum degree at most 2 (equivalently, a disjoint union of paths). Note that we can partition the vertex set of a forest into two independent sets. However, a pair of independent sets combined may not induce a forest. Thus our result extends the result of Wang and Xu (2013) stating that the vertex set of every planar graph without 4-cycles and 6-cycles can be partitioned into three sets, where one induces a graph with maximum degree two, and the remaining two are independent sets.