[日時] 2024年10月1日(火) 13:00--14:00
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 井上 裕太, 宮下 敦行 (東京大学)
[題目(Title)] Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
[概要(Abstract)]
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (non-trivial) snark that can be embedded in the projective plane is the Petersen graph.
This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex $v$ in a cubic graph $G$ is the operation that takes a 2-connected planar (cubic) multigraph $H$ containing some vertex $u$ of degree 3, unifying $G-v$ and $H-u$, and connecting the vertices in $N_G[v]$ in $G-v$ with the three neighbors of $u$ in $H-u$ with 3 edges. Any graph obtained in such a way is said to be "Petersen-like".
This result is a 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.
Using this result, we obtain the following algorithmic consequence.
- Input: A cubic graph $G$
- Output: Either a 3-edge-coloring of $G$, an obstruction showing that $G$ is not 3-edge-colorable, or the conclusion that $G$ cannot be embedded in the projective plane (certified by exposing a forbidden minor for the projective plane contained in $G$).
- Time complexity: $O(n^2)$, where $n = |V(G)|$
An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane.