Jaeger's modular orientation conjecture

High ★★★ Graph Theory » Coloring » Nowhere-zero flows

Author: Jaeger, Francois— posted by mdevos on 2007-03-07

Status disproved high confidence

Jaeger's modular orientation conjecture was refuted for $k \geq 3$: Han, Li, Wu, and Zhang (2018) constructed $4k$-edge-connected graphs admitting no modular $(2k+1)$-orientation for every $k \geq 3$, and even $(4k+1)$-edge-connected counterexamples for $k \geq 5$. The special cases $k=1$ (Tutte's 3-flow conjecture) and $k=2$ remain open; the $k=2$ instance was verified asymptotically almost surely for random 9-regular graphs by Delcourt, Huq, and Prałat (2022).

Cited literature (2)

counterexample Counterexamples to Jaeger's Circular Flow Conjecture (2018)

Miaomiao Han, Jiaao Li, Yezhou Wu, Cunquan Zhang · Journal of Combinatorial Theory, Series B

For every integer $k \geq 3$ constructs a $4k$-edge-connected graph that admits no modular $(2k+1)$-orientation, directly disproving Jaeger's conjecture; for $k \geq 5$ even $(4k+1)$-edge-connected counterexamples exist.
partial Almost all 9-regular graphs have a modulo-5 orientation (2022)

Michelle Delcourt, Reaz Huq, Pawel Pralat · arXiv preprint · arXiv:2210.12103 · doi:10.48550/arXiv.2210.12103

Using the small subgraph conditioning method, proves Jaeger's conjecture for $k=2$ (modulo-5 orientation of 9-regular graphs) holds asymptotically almost surely for random 9-regular graphs, extending the $k=1$ result of Pralat-Wormald.

Reviewer notes. Jaeger's circular flow conjecture (every $4k$-edge-connected graph has a circular flow of value at most $2+1/k$) is equivalent to the modular orientation conjecture by Jaeger's own observation, so the Han-Li-Wu-Zhang counterexamples apply directly. The partial positive result of Lovász, Thomassen, Wu, and Zhang (2013, JCTB) — that every $6k$-edge-connected graph has a modular $(2k+1)$-orientation — could not be verified via a readable URL (all WVU/ScienceDirect fetches returned binary or 403); it is mentioned in notes only. The conjecture survives only for $k=1$ (equivalent to Tutte's 3-flow conjecture, still open for 4-edge-connected graphs) and $k=2$ (still fully open). The Noga Alon paper on quasi-random regular graphs (Princeton preprint) was found but not successfully fetched.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 02) (web search enabled).

Conjecture. Every $ 4k $ - edge-connected graph can be oriented so that $ {\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0 $ (mod $ 2k+1 $ ) for every vertex $ v $ .

Keywords: nowhere-zero flow · orientation

Discussion

Jaeger called an orientation with the above property a modular $ (2k+1) $ - orientation , and observed that a graph has a modular $ (2k+1) $ -orientation if and only if it has a $ (2+\frac{1}{k}) $ -flow. Thus, this conjecture may be seen as a sharp form of the 2+epsilon flow conjecture . For k=1, this problem is precisely the 3-flow conjecture , and for k=2, Jaeger showed that this conjecture (if true) would imply the 5-flow conjecture . If true, this conjecture would be best possible for every value of k. The restriction of this conjecture to planar graphs is open, and has a dual formulation. See Mapping planar graphs to odd cycles .

Bibliography

[J] F. Jaeger, On circular flows in graphs. Finite and infinite sets, Vol. I, II (Eger, 1981), 391--402, Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam, 1984.. MathSciNet MathSciNet