Determining the circular flow number of a cubic graph
Summary: 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.
- Balanced Valuations and Flows in Multigraphs
- Beyond the flow decomposition barrier
- Computational results and new bounds for the circular flow number of snarks
- Counterexamples to Jaeger's circular flow conjecture
- scientific article; zbMATH DE number 3904637 (Why is no real title available?)
- Nowhere-zero 6-flows
- On (k,d)-colorings and fractional nowhere-zero flows
- On the degrees of the vertices of a directed graph
- Pathwidth of cubic graphs and exact algorithms
- Real flow number and the cycle rank of a graph
- The NP-Completeness of Edge-Coloring
- The number of fixed points of the majority rule
- The circular flow number of a 6-edge connected graph is less than four
- Flow number and circular flow number of signed cubic graphs
- Construction of graphs with given circular flow numbers
- Bounded-excess flows in cubic graphs
- Circular flow number of Goldberg snarks
- A lower bound for the complex flow number of a graph: a geometric approach
- Computational results and new bounds for the circular flow number of snarks
This page was built for publication: Determining the circular flow number of a cubic graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656904)
