Two strong 3-flow theorems for planar graphs

DOI10.4310/JOC.2022.V13.N4.A1MaRDI QIDQ2166386zbMATH OpenOpenAlexWikidataFDO

Authors J. V. de Jong

Publication date 24 August 2022

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.02140

zbMATH Keywords

planar graph\(\mathbb{Z}_3\)-connected graph\(3\)-flowmodulo-\(3\) orientation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)

Abstract: 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 (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'asz 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"otzsch'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.

Recommendations

• Strong 3‐Flow Conjecture for projective planar graphs
• Flow extensions and group connectivity with applications
• Nowhere-zero 3-flows in toroidal graphs
• A note on nowhere-zero 3-flows and \(Z_3\)-connectivity
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(6)

• Flow extensions and group connectivity with applications
• Some flow-equivalent planar and non-planar graphs
• Nowhere-zero 3-flows in signed planar graphs
• Nowhere-zero 3-flows in toroidal graphs
• Strong 3‐Flow Conjecture for projective planar graphs
• The weak 3-flow conjecture and the weak circular flow conjecture

This page was built for publication: Two strong 3-flow theorems for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2166386)