3-Flows with Large Support

Abstract

We prove that every 3-edge-connected graph $G$ has a 3-flow $\varphi$ with the property that $|\mathrm{supp}(\varphi )|\ge \frac{5}{6}|E(G)|$. The graph $K_4$ demonstrates that this $\frac{5}{6}$ ratio is best possible; there is an infinite family where $\frac{5}{6}$ is tight.

55 pages, 38 figures

Cited by in corpus (1)

• Sublinear bounds for nullity of flows and approximating Tutte's flow conjectures