论文标题
无需$ 4 $ -CYCLES和$ 5 $ CYCLE的平面图划分为有限度森林
Partitioning planar graphs without $4$-cycles and $5$-cycles into bounded degree forests
论文作者
论文摘要
1976年，斯坦伯格（Steinberg）猜想，没有$ 4 $ CYCLES和5美元的Cycles的平面图为$ 3 $ - 可油。这种猜想吸引了大约40年的众多研究人员，直到Cohen-Addad等人最近反驳。 （2017）。但是，对周期长度有限制的着色平面图仍然是研究的活跃领域，并且对此特定图类别的兴趣仍然存在。让$ g $为平面图，没有$ 4 $ - 周期和$ 5 $ -CYCLE。 For integers $d_1$ and $d_2$ satisfying $d_1+d_2\geq8$ and $d_2\geq d_1\geq 2$, it is known that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$, where each $V_i$ induces a graph with maximum degree at most $d_i$.由于斯坦伯格的猜想是错误的，因此将$ v（g）$的分区分为两套，其中一个诱导了一个空图，另一个则不能保证森林。我们的主要定理是在上述两个研究方向的交汇处。我们证明，$ v（g）$可以分为两组$ v_1 $和$ v_2 $，其中$ v_1 $最高$ 3 $，最高$ 3 $，$ v_2 $诱导森林，最高$ 4 $，最高学位；这既是斯坦伯格的猜想的放松，又是Sittitrai and Nakprasit（2019）以更强的形式加强结果。
In 1976, Steinberg conjectured that planar graphs without $4$-cycles and $5$-cycles are $3$-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by Cohen-Addad et al. (2017). However, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains. Let $G$ be a planar graph without $4$-cycles and $5$-cycles. For integers $d_1$ and $d_2$ satisfying $d_1+d_2\geq8$ and $d_2\geq d_1\geq 2$, it is known that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$, where each $V_i$ induces a graph with maximum degree at most $d_i$. Since Steinberg's Conjecture is false, a partition of $V(G)$ into two sets, where one induces an empty graph and the other induces a forest is not guaranteed. Our main theorem is at the intersection of the two aforementioned research directions. We prove that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$, where $V_1$ induces a forest with maximum degree at most $3$ and $V_2$ induces a forest with maximum degree at most $4$; this is both a relaxation of Steinberg's conjecture and a strengthening of results by Sittitrai and Nakprasit (2019) in a much stronger form.
