Flow-critical graphs

Abstract

Lovász et al. proved that every $6$-edge-connected graph has a nowhere-zero $3$-flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $3$-flow that extends the flow prescribed on the incident edges of a single vertex $z$ with bounded degree. We extend this theorem of Lovász et al. to allow $z$ to have arbitrary degree, but with the additional assumption that there is another vertex $x$ with large degree and no small cut separating $x$ and $z$. Using this theorem, we prove two results regarding the generation of minimal graphs with the property that prescribing the edges incident to a vertex with specific flow does not extend to a nowhere-zero $3$-flow. We use this to further strengthen the theorem of Lovász et al., as well as make progress on a conjecture of Li et al.

52 pages, in Journal of Graph Theory