The Flow Index of Regular Class I Graphs
Jiaao Li, Xueliang Li, Meiling Wang · SIAM Journal on Discrete Mathematics · 2022
For integers $k$ and $d$ with $k\ge 2d>0$, a circular ${k}/{d}$-flow of a graph $G$ is an orientation together with a mapping from $E(G)$ to $\{\pm d, \pm (d+1),\ldots,\pm (k-d)\}$ such that, for each vertex of $G$, the sum of images on outgoing edges is equal to the sum of images on incoming edges. Related to the four color problem, a classical result of Tutte shows that a cubic graph admits a circular $4/1$-flow if and only if it is Class I (i.e., $3$-edge-colorable). Tutte's $3$-flow conjecture implies that every $5$-regular Class I graph admits a nowhere-zero $3$-flow (equivalently, a circular $6/2$-flow) as a special case. Steffen in 2015 conjectured that every $(2t+1)$-regular Class I graph admits a circular $(2t+2)/t$-flow. He also proposed a more general conjecture that every $(2t+1)$-odd-edge-connected $(2t+1)$-regular graph admits a circular $(2t+2)/t$-flow for any integer $t\ge 2$, which includes the circular flow conjecture of Jaeger (1981) stating that every $2t$-edge-connected graph admits a circular $(2t+2)/t$-flow for any even $t\ge 2$. Jaeger's conjecture was disproved in 2018 for all even $t\ge 6$, and based on these results, Mattiolo and Steffen recently constructed counterexamples to Steffen's conjecture for Class I graphs when $t=4k+2$ for any integer $k\ge 1$. In this paper, we extend the above results and construct infinitely many $2t$-edge-connected $(2t+1)$-regular Class I graphs without circular $(2t+2)/t$-flows for any integer $t\in \{6,8,10\}$ or $t\geq 12$. Our result provides more general counterexamples to Steffen's two conjectures for both even and odd $t$ and simultaneously generalizes the counterexamples of Jaeger's circular flow conjecture to regular Class I graphs.