Decomposing planar graphs into graphs with degree restrictions

Abstract

Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d,h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d\le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3\le 4$, $h_2\le 8$, and $h_1=\infty$. This paper proves that $h_4=1,h_3=2$, and $4\le h_2\le 6$.

16 pages, 5 figures