In 1972 Tutte famously conjectured that every 4-edge-connected graph has a nowhere-zero 3-flow; this is known to be equivalent to every 5-regular, 4-edge-connected graph having an edge orientation in which every in-degree is either 1 or 4. Jaeger conjectured a generalization of Tutte's nowhere-zero 3-flow conjecture, namely, that every $(4p+1)$-regular, $4p$-edge-connected graph has an edge orientation in which every in-degree is either $p$ or $3p+1$. Inspired by the work of Prałat and Wormald investigating $p=1$, we address $p=2$ to show that the conjecture holds asymptotically almost surely for random 9-regular graphs. It follows that the conjecture holds for almost all 9-regular, 8-edge-connected graphs. These results make use of the technical small subgraph conditioning method.
@article{10_37236_12513,
author = {Michelle Delcourt and Reaz Huq and Pawe{\l} Pra{\l}at},
title = {Almost all 9-regular graphs have a modulo-5 orientation},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/12513},
zbl = {1565.05097},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12513/}
}
TY - JOUR
AU - Michelle Delcourt
AU - Reaz Huq
AU - Paweł Prałat
TI - Almost all 9-regular graphs have a modulo-5 orientation
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12513/
DO - 10.37236/12513
ID - 10_37236_12513
ER -
%0 Journal Article
%A Michelle Delcourt
%A Reaz Huq
%A Paweł Prałat
%T Almost all 9-regular graphs have a modulo-5 orientation
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12513/
%R 10.37236/12513
%F 10_37236_12513
Michelle Delcourt; Reaz Huq; Paweł Prałat. Almost all 9-regular graphs have a modulo-5 orientation. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/12513
