Journal of Combinatorics

Volume 13 (2022)

Number 4

Two strong 3-flow theorems for planar graphs

Pages: 445 – 479

DOI: https://dx.doi.org/10.4310/JOC.2022.v13.n4.a1

Author

J. V. de Jong (Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada; and Department of Mathematical and Computational Sciences, University of Toronto, Mississauga, Ontario, Canada)

Abstract

In 1972, Tutte posed the 3-Flow Conjecture, which states 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 (we call this the Strong 3-Flow Conjecture). 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 the 3-Flow and Strong 3-Flow 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 provide two extensions to their result, that we developed in order to prove the Strong 3-Flow Conjecture for projective planar graphs.

Keywords

$3$-flow, modulo-$3$ orientation, $\mathbb{Z}_3$-connected, planar graph

2010 Mathematics Subject Classification

05C21

Received 28 November 2020

Accepted 4 July 2021

Published 18 August 2022