Nowhere-zero $3$-flows in graphs with forbidden edge-cuts

Abstract

Tutte's $3$-flow conjecture asserts that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In 2013, Lovász, Thomassen, Wu, and Zhang proved that every odd-$7$-edge-connected graph admits a nowhere-zero $3$-flow; consequently, the conjecture holds for $4$-edge-connected graphs with no edge-cut of size $5$. We consider the complementary situation in which $5$-edge-cuts are allowed. We show that, when edge-cuts of size $5$ are permitted, Tutte's $3$-flow conjecture holds for graphs with no edge-cut of any size from $6$ to k, where k is an absolute constant. In fact, k=40 suffices and we prove a stronger version in which only nontrivial edge-cuts of those sizes are forbidden. A graph is called essentially t-edge-connected if deleting any set of at most t−1 edges leaves at most one nontrivial component. Motivated by Jaeger's weak $3$-flow conjecture, we prove an analogous result for essential edge connectivity: every $4$-edge-connected, essentially $41$-edge-connected graph admits a nowhere-zero $3$-flow.

On nowhere-zero 3-flows in Cayley graphs on groups of order p²n
Milad Ahanjideh, István Kovács
arXiv30 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
A nowhere-zero point for several linear mappings simultaneously
Amir Jafari
arXiv17 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The forbidden structure for zero forcing number
Carlos A. Alfaro, Michael D. Barrus, Sergio Gerardo Gómez-Galicia +5
arXiv28 Aug 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A finite forbidden family with superlinear surplus and non-join extremal graphs
Chuandong Xu
arXiv6 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Maximizing the number of cliques in K_r+1-free graphs with forbidden properties
Aleyah Dawkins, Rachel Kirsch
arXiv21 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{li2026nowherezero,
  title = {{Nowhere-zero $3$-flows in graphs with forbidden edge-cuts}},
  author = {Jiaao Li and Xinyuan Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08377},
  eprint = {2609.08377},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08377},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Nowhere-zero $3$-flows in graphs with forbidden edge-cuts
AU  - Jiaao Li
AU  - Xinyuan Li
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08377
UR  - https://arxiv.org/abs/2609.08377
AB  - Tutte's $3$-flow conjecture asserts that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In 2013, Lovász, Thomassen, Wu, and Zhang proved that every odd-$7$-edge-connected graph admits a nowhere-zero $3$-flow; consequently, the conjecture holds for $4$-edge-connected graphs with no edge-cut of size $5$. We consider the complementary situation in which $5$-edge-cuts are allowed. We show that, when edge-cuts of size $5$ are permitted, Tutte's $3$-flow conjecture holds for graphs with no edge-cut of any size from $6$ to k, where k is an absolute constant. In fact, k=40 suffices and we prove a stronger version in which only nontrivial edge-cuts of those sizes are forbidden. A graph is called essentially t-edge-connected if deleting any set of at most t−1 edges leaves at most one nontrivial component. Motivated by Jaeger's weak $3$-flow conjecture, we prove an analogous result for essential edge connectivity: every $4$-edge-connected, essentially $41$-edge-connected graph admits a nowhere-zero $3$-flow.
ER  -

Abstract

Related

Cite