The structure of graphs with Circular flow number 5 or more

Giuseppe Mazzuoccolo
Università di Modena e Reggio Emilia

Louis Esperet
Laboratoire G-SCOP (Grenoble-INP, CNRS) France

Michael Tarsi
The Blavatnik School of Computer Science, Tel Aviv University, Israel



Content: For some time the Petersen graph was the only known Snark, with circular flow number $5$ (or more, as long as Tutte's $5$-flow Conjecture is in doubt). Although infinitely many such snarks were presented in "Macajova-Raspaud On the Strong Circular 5-Flow Conjecture JGT 52 (2006)", eight years ago, the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. Here, we first perform an analysis of sets of flow values, which can be transferred through flow networks, with the flow capacity of each edge restricted to the open interval $(1,4)$ modulo $5$. All these sets are symmetric unions, of open integer intervals in the ring $\mathbb{R}/5\mathbb{Z}$. We use the results to design an arsenal of methods for constructing snarks $S$, with circular flow number $\phi_c(S)\ge 5$. As one indication to the diversity and density of the obtained family of graphs, we show that it is rich enough for proving NP-completeness of the corresponding recognition problem.

Back to all abstracts