2020/11/02 by Jamie V. de Jong, de Jong, Jamie V., R. Bruce Richter +1
Computer Science · #05C21 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2011.00672
openalex publication_date 2020/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1972, Tutte posed the 3-Flow Conjecture: that all 4-edge-connected graphs have a nowhere zero 3-flow. This was extended by Jaeger et al.(1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo 3) between the inflow and outflow. They conjectured that all 5-edge-connected graphs with a valid prescription function have a nowhere zero 3-flow meeting that prescription. Kochol (2001) showed that replacing 4-edge-connected with 5-edge-connected would suffice to prove the 3-Flow Conjecture and Lovász et al.(2013) showed that both conjectures hold if the edge connectivity condition is relaxed to 6-edge-connected. Both problems are still open for 5-edge-connected graphs. The 3-Flow Conjecture was known to hold for planar graphs, as it is the dual of Grötzsch's Colouring Theorem. Steinberg and Younger (1989) provided the first direct proof using flows for planar graphs, as well as a proof for projective planar graphs. Richter et al.(2016) provided the first direct proof using flows of the Strong 3-Flow Conjecture for planar graphs. We prove the Strong 3-Flow Conjecture for projective planar graphs.