The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem

DOI10.4310/JOC.2016.V7.N2.A12MaRDI QIDQ286768zbMATH OpenOpenAlexFDO

Authors L. Esperet, Michael Tarsi, G. Mazzuoccolo

Publication date 25 May 2016

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.03774

zbMATH Keywords

NP-completenesssnarkscircular flowsnowhere-zero flows

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21) Structural characterization of families of graphs (05C75)

Abstract: For some time the Petersen graph has been the only known Snark with circular flow number $5$ (or more, as long as the assertion of Tutte's $5$-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago by Macajova and Raspaud, the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval $(1,4)$ modulo $5$. All these sets are symmetric unions of open integer intervals in the ring $mathbbR/5mathbbZ$. We use the results to design an arsenal of methods for constructing snarks $S$ with circular flow number $ph{i}_c(S)ge5$. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete.

Recommendations

• Recognizing recursive circulant graphs (extended abstract)
• Construction of graphs with given circular flow numbers
• On circular flows of graphs
• The Set of Circular Flow Numbers of Regular Graphs
• Circular flow numbers of regular multigraphs
• scientific article; zbMATH DE number 3904637
• On circle graphs with girth at least five
• Classification of efficient dominating sets of circulant graphs of degree 5
• On the strong circular 5‐flow conjecture

Cited in

(8)

• Circular flow number of Goldberg snarks
• On the strong circular 5‐flow conjecture
• Measures of edge-uncolorability of cubic graphs
• Cubic graphs that cannot be covered with four perfect matchings
• Computational results and new bounds for the circular flow number of snarks
• A unified approach to construct snarks with circular flow number 5
• On \(\mathbb{Z}\)-flow-continuous maps and oriented colorings of cubic graphs
• Treelike snarks

This page was built for publication: The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286768)