Circular flow number of regular class 1 graphs

Status disproved high confidence

Mattiolo and Steffen (J. Graph Theory, 2022) explicitly disproved Steffen's conjecture by constructing $(2t+1)$-regular class 1 graphs with circular flow number greater than $2+\frac{2}{t}$; the counterexamples are built from a family of graphs originally used to disprove Jaeger's Circular Flow Conjecture and apply to $t = 4k+2$ for all integers $k \geq 1$. A subsequent SIAM (2022) paper by Li, Li, and Wang on the 'flow index of regular Class I graphs' extends the family of counterexample values of $t$ further; however, the conjecture remains true for $t=1$ (cubic graphs), and the exact set of $t$ for which it holds is still under investigation.

Cited literature (1)

• counterexample Edge colorings and circular flows on regular graphs (2022)
  Davide Mattiolo, Eckhard Steffen · Journal of Graph Theory · arXiv:2001.02484 · doi:10.1002/jgt.22746

  Disproves the conjecture that every $(2t+1)$-regular class 1 graph has circular flow number at most $2+2/t$, and also confirms that $2+2/(2t-1)$ is the infimum of circular flow numbers for $(2t+1)$-regular class 2 graphs.

Reviewer notes. A second 2022 paper, 'The Flow Index of Regular Class I Graphs' by Jiaao Li, Xueliang Li, and Meiling Wang (SIAM J. Discrete Math.), is cited across multiple sources as extending the counterexamples to t in {6,8,10} and all t≥12; but I could not verify this paper via any accessible URL (the PDF hosts returned binary content and the SIAM page returned 403), so it is excluded from since_posted. The disproof in the verified Mattiolo–Steffen paper applies to t = 4k+2 for k ≥ 1 (i.e., t ∈ {6,10,14,…}); the arXiv page lists the journal version as Journal of Graph Theory 99 (2022), 399-413, DOI 10.1002/jgt.22746. The conjecture is still true for t=1 and its status for t ∈ {2,3,4,5} and odd t > 5 is not fully resolved.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (web search enabled) · 174s.