Partitioning edges of a planar graph into linear forests and a matching

02/26/2023

∙

by   Marthe Bonamy, et al.

∙

0

∙

share

We show that the edges of any planar graph of maximum degree at most 9 can be partitioned into 4 linear forests and a matching. Combined with known results, this implies that the edges of any planar graph G of odd maximum degree Δ≥ 9 can be partitioned into Δ-12 linear forests and one matching. This strengthens well-known results stating that graphs in this class have chromatic index Δ [Vizing, 1965] and linear arboricity at most ⌈(Δ+1)/2⌉ [Wu, 1999].