Circular flow numbers of $r$-graphs

Status disproved high confidence

The conjecture was effectively disproved by Mattiolo and Steffen (2022), who constructed $(2t+1)$-regular class-1 graphs with circular flow number exceeding $2 + 2/t$ for $t = 4k+2$ ($k \geq 1$). The OPG discussion itself notes that every $(2t+1)$-regular class-1 graph is a $(2t+1)$-graph (r-graph), so these are also counterexamples to the stated conjecture; the same paper confirmed that $2 + 2/(2t-1)$ is the infimum of circular flow numbers for $(2t+1)$-regular class-2 graphs.

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

  Constructs $(2t+1)$-regular class-1 graphs with $F_c > 2+2/t$ for $t = 4k+2$ ($k \geq 1$), disproving the class-1 version of Steffen's conjecture; since the OPG itself observes that every $(2t+1)$-regular class-1 graph is a $(2t+1)$-graph, these serve as counterexamples to the r-graph conjecture as well, and the paper also confirms that $2+2/(2t-1)$ is the infimum of circular flow numbers for $(2t+1)$-regular class-2 graphs.

Reviewer notes. The disproof is indirect but rigorous: it follows from the OPG's own stated implication (every $(2t+1)$-regular class-1 graph is a $(2t+1)$-graph) together with Mattiolo-Steffen's class-1 counterexamples for t = 4k+2. The arXiv page verifies the abstract's disproof claim and lists the journal version as Journal of Graph Theory 99 (2022), 399-413, DOI 10.1002/jgt.22746. A SIAM 2022 paper by Li, Li, Wang ('Flow index of regular class I graphs') appeared in searches but its PDF was unreadable; it may contain additional relevant results. The case t = 2 (Tutte's 3-flow conjecture) was explicitly noted as an instance of the OPG conjecture and remains open.

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