Determining the circular flow number of a cubic graph

Robert Lukoťka

The electronic journal of combinatorics, Tome 28 (2021) no. 1

Résumé

A circular nowhere-zero $r$-flow on a bridgeless graph $G$ is an orientation of the edges and an assignment of real values from $[1, r-1]$ to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number, $\phi_c(G)$, of $G$ is the infimum over all values $r$ such that $G$ admits a nowhere-zero $r$-flow. A flow has its underlying orientation. If we subtract the number of incoming and the number of outgoing edges for each vertex, we get a mapping $V(G) \to \mathbb{Z}$, which is its underlying balanced valuation. In this paper we describe efficient and practical polynomial algorithms to turn balanced valuations and orientations into circular nowhere zero $r$-flows they underlie with minimal $r$. Using this algorithm one can determine the circular flow number of a graph by enumerating balanced valuations. For cubic graphs we present an algorithm that determines $\phi_c(G)$ in case that $\phi_c(G) \leqslant 5$ in time $O(2^{0.6\cdot|V(G)|})$. If $\phi_c(G) > 5$, then the algorithm determines that $\phi_c(G) > 5$ and thus the graph is a counterexample to Tutte's $5$-flow conjecture. The key part is a procedure that generates all (not necessarily proper) $2$-vertex-colourings without a monochromatic path on three vertices in $O(2^{0.6\cdot|V(G)|})$ time. We also prove that there is at most $2^{0.6\cdot|V(G)|}$ of them.

Détail

DOI : 10.37236/9607

Classification : 05C21, 05C30, 05C85
Mots-clés : bridgeless graph, polynomial algorithms