论文标题
（1,0,0） - 平面图的可溶性，没有长度为4或6的循环
(1,0,0)-colorability of planar graphs without cycles of length 4 or 6
论文作者
论文摘要
A graph $G$ is $(d_1,d_2,d_3)$-colorable if the vertex set $V(G)$ can be partitioned into three subsets $V_1,V_2$ and $V_3$ such that for $i\in\{1,2,3\}$, the induced graph $G[V_i]$ has maximum vertex-degree at most $d_i$.因此，$（0,0,0）$ - 可着色性正是3色。 众所周知的斯坦伯格的猜想指出，每个平面图没有长度为4或5的循环，都是3个色的。由于该猜想在2017年被Cohen-Addad等反驳，因此，对于给定的$ i \ in \ {6，\ ldots，9 \} $的每个没有长度4或$ i $ $ $ $ $ $ $ $的平面图是3个上色的一个类似的问题。在本文中，我们从不当着色的角度考虑了$ i = 6 $的情况。更确切地说，我们证明每个平面图没有长度为4或6的循环为（1,0,0） - 可溶性，这改善了早期结果，它们是（2,0,0）可（2,0,0） - 可溶性，并且（1,1,1,0）可溶于（1,1,0） - 可溶于4至6的平面图，而没有4到6的平面图。
A graph $G$ is $(d_1,d_2,d_3)$-colorable if the vertex set $V(G)$ can be partitioned into three subsets $V_1,V_2$ and $V_3$ such that for $i\in\{1,2,3\}$, the induced graph $G[V_i]$ has maximum vertex-degree at most $d_i$. So, $(0,0,0)$-colorability is exactly 3-colorability. The well-known Steinberg's conjecture states that every planar graph without cycles of length 4 or 5 is 3-colorable. As this conjecture being disproved by Cohen-Addad etc. in 2017, a similar question, whether every planar graph without cycles of length 4 or $i$ is 3-colorable for a given $i\in \{6,\ldots,9\}$, is gaining more and more interest. In this paper, we consider this question for the case $i=6$ from the viewpoint of improper colorings. More precisely, we prove that every planar graph without cycles of length 4 or 6 is (1,0,0)-colorable, which improves on earlier results that they are (2,0,0)-colorable and also (1,1,0)-colorable, and on the result that planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable.
