Nowhere-zero flow reconfiguration
By: Louis Esperet, Aurélie Lagoutte, Margaux Marseloo
We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero $k$-flows of a given graph $G$ are connected by a sequence of nowhere-zero $k$-flows of $G$, such that any two consecutive flows in the sequence differ only on a cycle of $G$. We conjecture that any two nowhere-zero 5-flows in any 2-edge-connected graph are connected in this way. This can be seen as a reconfiguration variant of Tutte's 5-flow conjecture. We study this problem in the setting of integer flows and group flows, and show that the structure of groups affects the answer, contrary to the existence of nowhere-zero flows. We also highlight a duality with recoloring in planar graphs and deduce that any two nowhere-zero 7-flows in a planar graph are connected, among other results. Finally we show that for any graph $G$, there is an abelian group $A$ such that all nowhere-zero $A$-flows in $G$ are connected, which is a weak form of our original conjecture. We conclude with several problems and conjectures.
Similar Papers
Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
Data Structures and Algorithms
Makes computer problems easier to solve.
Flipping odd matchings in geometric and combinatorial settings
Computational Geometry
Lets you change one matching to another.
Determining a graph from its reconfiguration graph
Combinatorics
Lets computers know graphs from color patterns.