Lifting nowhere-zero $\mathbb{Z}_k$-flows to integer $k$-flows on signed graphs without long barbells for even $k\ge 6$ (Problem 3.14 of Lu–Luo–Schubert–Steffen–Zhang)

For unsigned graphs, a classical theorem of Tutte states that a nowhere-zero flow over the cyclic group $\mathbb{Z}_k$ can always be lifted to a nowhere-zero integer $k$ -flow whose edge values are congruent to the original ones modulo $k$ ; this equivalence between modular and integer flows fails for signed graphs in general. Lu, Luo, Schubert, Steffen and Zhang (SIAM J. Discrete Math., 2020) proved that for signed graphs without long barbells — signed graphs containing no two vertex-disjoint unbalanced circuits joined by a path — every nowhere-zero $\mathbb{Z}_k$ -flow with odd $k\ge 3$ lifts edge-wise congruently to an integer $k$ -flow, and that a weaker existence-level equivalence holds for $k=3$ and all $k\ge 5$ . Their Problem 3.14 asks whether the edge-wise congruent lifting also holds for every even $k\ge 6$ on this family.

Background

A signed graph $(G,\sigma)$ is a graph $G$ whose edges carry signs: a signature $\sigma$ maps each edge to $+1$ or $-1$ . A circuit (a connected 2-regular subgraph) is called balanced if it contains an even number of negative edges and unbalanced otherwise; this parity is unchanged by switching, i.e. reversing the signs of all edges at a chosen vertex, so balance is an invariant of the switching class. Flows on signed graphs are defined using Bouchet's bidirected orientation convention: an orientation $\tau$ assigns a direction to each half-edge so that the two half-edges of an edge $e=uv$ point consistently through the edge when $\sigma(e)=+1$ and in a switched, bidirected way when $\sigma(e)=-1$ (formally, $\tau(h_{ue})\tau(h_{ve})=-\sigma(e)$ ). A flow is then a mapping $f:E(G)\to\mathbb{R}$ whose boundary $\partial(\tau,f)(v)=\sum_{h\in H(v)}\tau(h)\,f(e_h)$ , summed over the half-edges at $v$ , vanishes at every vertex — the signed-graph analogue of Kirchhoff's conservation law. A flow is nowhere-zero if $f(e)\ne 0$ for every edge; a nowhere-zero integer $k$ -flow takes values in $\{\pm 1,\dots,\pm(k-1)\}$ , and a nowhere-zero $\mathbb{Z}_k$ -flow (modulo $k$ -flow) takes values in the cyclic group $\mathbb{Z}_k\setminus\{0\}$ with all vertex boundaries vanishing modulo $k$ . A signed graph is flow-admissible if it admits a nowhere-zero $k$ -flow for some $k$ ; Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow.

For unsigned graphs, Tutte's equivalence — a graph admits a nowhere-zero $\mathbb{Z}_k$ -flow if and only if it admits a nowhere-zero integer $k$ -flow, and moreover every $\mathbb{Z}_k$ -flow can be lifted to an integer $k$ -flow with the same values modulo $k$ on every edge (see Younger's exposition) — is a cornerstone of flow theory: it lets arguments proved for modular flows, the setting of most landmark results such as Seymour's 6-flow theorem, transfer verbatim to integer flows. For signed graphs the equivalence fails in general: Bouchet proved only that a $\mathbb{Z}_k$ -flow guarantees a $2k$ -flow, and a signed wheel $W_5$ (a 5-cycle with a hub vertex joined to every rim vertex) is known that admits a nowhere-zero $\mathbb{Z}_4$ -flow but no nowhere-zero 4-flow. The failure is tied to a structural feature with no unsigned counterpart: a long barbell is the union of two vertex-disjoint unbalanced circuits together with a path that meets each circuit only at its ends; such a subgraph is the support of a 3-flow but not of a 2-flow, whereas in an unsigned graph every circuit supports a 2-flow.

Lu, Luo, Schubert, Steffen and Zhang studied the family of flow-admissible signed graphs without long barbells, which in several respects behaves like an unsigned graph. They proved: (Theorem 3.3) every such signed graph admits a nowhere-zero 6-flow, verifying Bouchet's conjecture for this family; (Theorem 3.4) for $k=3$ and every $k\ge 5$ , such a signed graph admits a nowhere-zero $\mathbb{Z}_k$ -flow if and only if it admits a nowhere-zero integer $k$ -flow — an existence-level analogue of Tutte's equivalence whose $k\ge 6$ part is derived from the 6-flow theorem and therefore yields no relation between the values of the two flows; and (Theorem 3.5) for every odd $k\ge 3$ , every nowhere-zero $\mathbb{Z}_k$ -flow $(\tau,f_1)$ of such a signed graph lifts to a nowhere-zero integer $k$ -flow $(\tau,f_2)$ with $f_2(e)\equiv f_1(e)\pmod{k}$ for every edge $e$ — the full edge-wise form of Tutte's equivalence. The case $k=4$ is excluded because the equivalence genuinely fails for it. Whether the edge-wise congruent lifting of Theorem 3.5 extends to even $k\ge 6$ is left open as Problem 3.14 of that paper and is the subject of this record. The odd- $k$ proof relies on parity arguments (for instance, analyzing the boundary structure of a minimal counterexample via dipaths and tadpole-shaped subgraphs) that have no direct analogue when the modulus is even.

Problem Statement

For every even integer $k\ge 6$ : given a signed graph $(G,\sigma)$ that contains no long barbells (no two vertex-disjoint unbalanced circuits joined by a path meeting each only at its ends) and that admits a nowhere-zero $\mathbb{Z}_k$ -flow $(\tau,f_1)$ , does there necessarily exist a nowhere-zero integer $k$ -flow $(\tau,f_2)$ , with the same orientation $\tau$ , such that $f_2(e)\equiv f_1(e)\pmod{k}$ for every edge $e$ of $G$ ?

This is Problem 3.14 of Lu, Luo, Schubert, Steffen and Zhang (2020). An affirmative answer must hold uniformly: for all even $k\ge 6$ , all signed graphs without long barbells, and all nowhere-zero $\mathbb{Z}_k$ -flows. A negative answer is a single explicit counterexample: one even $k\ge 6$ , one signed graph without long barbells, and one nowhere-zero $\mathbb{Z}_k$ -flow $(\tau,f_1)$ such that no nowhere-zero integer $k$ -flow $(\tau,f_2)$ with $f_2(e)\equiv f_1(e)\pmod{k}$ exists. The analogous edge-wise lifting statement is known to be true for all odd $k\ge 3$ (Theorem 3.5 of the source paper), while for $k=4$ even the existence-level equivalence fails; the even case $k\ge 6$ is the remaining gap.

References

You Lu, Rong Luo, Michael Schubert, Eckhard Steffen, Cun-Quan Zhang. Flows on Signed Graphs without Long Barbells. SIAM Journal on Discrete Mathematics 34(4):2166–2182, 2020. DOI: 10.1137/18m1222818; arXiv:1908.11004. https://doi.org/10.1137/18m1222818
Miaomiao Han, Jiaao Li, You Lu, Rong Luo. Modulo Flows and Integer Flows in Signed Graphs. Journal of Graph Theory 110(2):167–173, 2025. DOI: 10.1002/jgt.23261. https://doi.org/10.1002/jgt.23261
You Lu, Rong Luo, Cun-Quan Zhang, Zhang Zhang. Signed Graphs, Nonorientable Surfaces, and Integer Flows. Journal of Graph Theory 110(1):48–58, 2025. DOI: 10.1002/jgt.23249. https://doi.org/10.1002/jgt.23249
You Lu, Rong Luo, Cun-Quan Zhang. Six-flows of signed graphs with frustration index three. Discrete Mathematics 348(2):114325, 2025. DOI: 10.1016/j.disc.2024.114325. https://doi.org/10.1016/j.disc.2024.114325
Rong Luo, Edita Máčajová, Martin Škoviera, Cun-Quan Zhang. An 8-Flow Theorem for Signed Graphs. SIAM Journal on Discrete Mathematics 39(3):1409–1417, 2025. DOI: 10.1137/24m1640513; arXiv:2402.12883. https://doi.org/10.1137/24m1640513
Liangchen Li, Chong Li, Rong Luo, Cun-Quan Zhang. Integer flows on triangularly connected signed graphs. Journal of Graph Theory 106(2):257–272, 2024. DOI: 10.1002/jgt.23076; arXiv:2310.13504. https://doi.org/10.1002/jgt.23076
Miaomiao Han, Jiaao Li, Rong Luo, Yongtang Shi, Cun-Quan Zhang. Integer Flows and Modulo Orientations of Signed Graphs. SIAM Journal on Discrete Mathematics 35(1):376–391, 2021. DOI: 10.1137/20M1317141. https://doi.org/10.1137/20M1317141
Chiara Cappello, Eckhard Steffen. Frustration-critical signed graphs. Discrete Applied Mathematics 322:183–193, 2022. DOI: 10.1016/j.dam.2022.08.010. https://doi.org/10.1016/j.dam.2022.08.010
Alejandra Brewer Castano, Jessica McDonald, Kathryn Nurse. Group Connectivity in 3-Edge-Connected Signed Graphs. SIAM Journal on Discrete Mathematics 39(1):388–412, 2025. DOI: 10.1137/23m1615218; arXiv:2306.04151. https://doi.org/10.1137/23m1615218
Matt DeVos, Jiaao Li, You Lu, Rong Luo, Cun-Quan Zhang, Zhang Zhang. Flows on flow-admissible signed graphs. Journal of Combinatorial Theory, Series B 149:198–221, 2021. DOI: 10.1016/j.jctb.2020.04.008; arXiv:1908.10853. https://doi.org/10.1016/j.jctb.2020.04.008
Jian Cheng, You Lu, Rong Luo, Cun-Quan Zhang. Signed graphs: from modulo flows to integer-valued flows. SIAM Journal on Discrete Mathematics 32(2):956–965, 2018. DOI: 10.1137/17m1126072; arXiv:1704.08739. https://doi.org/10.1137/17m1126072
Matt DeVos, Kathryn Nurse, Robert Šámal. Nowhere-zero 8-flows in 3-edge-connected signed graphs. Preprint, 2025. arXiv:2512.18923. https://arxiv.org/abs/2512.18923
Kathryn Nurse. Bouchet's conjecture for cyclically 5-edge-connected, cubic signed graphs. Preprint, 2026. arXiv:2601.05692. https://arxiv.org/abs/2601.05692
Chao Wen, Qiang Sun, Chao Zhang. Nowhere-zero flows on signed supereulerian graphs. Preprint, 2025. arXiv:2510.08192. https://arxiv.org/abs/2510.08192
André Bouchet. Nowhere-zero integral flows on a bidirected graph. Journal of Combinatorial Theory, Series B 34(3):279–292, 1983. DOI: 10.1016/0095-8956(83)90041-2. https://doi.org/10.1016/0095-8956(83)90041-2
P. D. Seymour. Nowhere-zero 6-flows. Journal of Combinatorial Theory, Series B 30(2):130–135, 1981. DOI: 10.1016/0095-8956(81)90058-7. https://doi.org/10.1016/0095-8956(81)90058-7
D. H. Younger. Integer flows. Journal of Graph Theory 7(3):349–357, 1983. DOI: 10.1002/jgt.3190070307. https://doi.org/10.1002/jgt.3190070307
W. T. Tutte. The Factorization of Linear Graphs. Journal of the London Mathematical Society s1-22(2):107–111, 1947. DOI: 10.1112/jlms/s1-22.2.107. https://doi.org/10.1112/jlms/s1-22.2.107

Search articles

Lifting nowhere-zero $\mathbb{Z}_k$ -flows to integer $k$ -flows on signed graphs without long barbells for even $k\ge 6$ (Problem 3.14 of Lu–Luo–Schubert–Steffen–Zhang)

Background

Problem Statement

References