论文标题
将平面图分解为具有度限制的图形
Decomposing planar graphs into graphs with degree restrictions
论文作者
论文摘要
给定图表$ g $，$ g $的分解是其边缘的分区。图形为$（d，h）$ - 如果可以将其边缘集分配为$ d $ - 定位图，并且最多最高$ h $的图形。对于$ d \ le 4 $，我们对最小整数$ h_d $感兴趣，因此每个平面图都是$（d，h_d）$ - 可分解的。众所周知，$ h_3 \ le 4 $，$ h_2 \ le 8 $和$ h_1 = \ infty $。本文证明$ h_4 = 1，h_3 = 2 $和$ 4 \ le H_2 \ le 6 $。
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$.
