# 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

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**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.