标题： 环面上的三边着色（Tait 着色）三次图：Grünbaum 猜想的证明 显示英文标题

标题： Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture

摘要： 我们证明了每一个可以嵌入到环面的4-圈连通三次图，除了一个称为“Petersen-like”的特殊图类外，都是3-边可着色的。 这意味着每个（非平凡的）环面上的snark都可以通过点积运算从若干个Petersen图的拷贝得到。 这个家族中的前两个snark分别是Petersen图和Blanuša snark之一；其余的由Vodopivec在2008年提出。 这证明了一个加强版的Grünbaum于1968年提出的著名且长期存在的猜想。 这意味着一个可以嵌入到环面的2-连通三次（多重）图如果不是3-边可着色的，当且仅当它可以通过用2-边连通平面三次（多重）图替换Petersen图的点积来获得。 这里，在三次图$G$中替换顶点$v$是指对一个 2-连通平面三次多重图$H$和其某个度数为 3 的顶点$u$执行的操作，该操作将$G-v$和$H-u$合并，并用匹配连接$v$在$G-v$中的邻居与$u$在$H-u$中的邻居。 这一结果是对四色定理的非常非平凡的一般化推广，其证明需要结合大量的计算机验证和无需计算机的现有可着色性证明扩展。 这一结果的一个重要推论是对于环面图的Tutte四流猜想的一个非常强的形式。 我们证明了嵌入到环面上的2-边连通图除非是Petersen-like（在这种情况下它不具有无零流的4-流），否则它总是存在一个无零流的4-流。 注意，这与环面上的Tutte四流猜想相比是一个巨大的加强，因为Tutte四流猜想假设图不包含Petersen图作为其子式，而几乎所有环面图都包含Petersen图子式，但几乎没有一个是Petersen-like的。 显示英文摘要

摘要： We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exceptional graph class called "Petersen-like", is 3-edge-colorable. This means every (non-trivial) toroidal snark can be obtained from several copies of the Petersen graph using the dot product operation. The first two snarks in this family are the Petersen graph and one of Blanu\v{s}a snarks; the rest are exposed by Vodopivec in 2008. This proves a strengthening of the well-known, long-standing conjecture of Gr\"unbaum from 1968. This implies that a 2-connected cubic (multi)graph that can be embedded in the torus is not 3-edge-colorable if and only if it can be obtained from a dot product of copies of the Petersen graph by replacing its vertices with 2-edge-connected planar cubic (multi)graphs. Here, replacing a vertex $v$ in a cubic graph $G$ is the operation that takes a 2-connected planar cubic multigraph $H$ and one of its vertices $u$ of degree 3, unifying $G-v$ and $H-u$ and connecting the neighbors of $v$ in $G-v$ with the neighbors of $u$ in $H-u$ with a matching. This result is a highly nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. An important consequence of this result is a very strong version of the Tutte 4-Flow Conjecture for toroidal graphs. We show that a 2-edge connected graph embedded in the torus admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). Observe that this is a vast strengthening over the Tutte 4-Flow Conjecture on the torus, which assumes that the graph does not contain the Petersen graph as a minor because almost all toroidal graphs contain the Petersen graph minor, but almost none are Petersen-like.