Abstract: For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for emph{snarks}, the class of nontrivial 3-regular graphs which cannot be 3-edge coloured. In the first part of this paper we present a new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on vertices. Previously lists up to vertices have been published. In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaeger's Petersen colouring conjecture, which in turn implies that Fulkerson's conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 446493 (Why is no real title available?)
- scientific article; zbMATH DE number 3851125 (Why is no real title available?)
- scientific article; zbMATH DE number 3937197 (Why is no real title available?)
- scientific article; zbMATH DE number 3952799 (Why is no real title available?)
- scientific article; zbMATH DE number 4075098 (Why is no real title available?)
- scientific article; zbMATH DE number 4106897 (Why is no real title available?)
- scientific article; zbMATH DE number 3728302 (Why is no real title available?)
- scientific article; zbMATH DE number 3754754 (Why is no real title available?)
- scientific article; zbMATH DE number 978847 (Why is no real title available?)
- scientific article; zbMATH DE number 2170455 (Why is no real title available?)
- scientific article; zbMATH DE number 227006 (Why is no real title available?)
- scientific article; zbMATH DE number 3390826 (Why is no real title available?)
- A note about the dominating circuit conjecture
- A note on semiextensions of stable circuits
- A survey on snarks and new results: Products, reducibility and a computer search
- Blocking and anti-blocking pairs of polyhedra
- Circle graphs and the cycle double cover conjecture
- Circuit double covers in special types of cubic graphs
- Compatible circuit decompositions of 4‐regular graphs
- Covering Multigraphs by Simple Circuits
- Cycle covers (I) - minimal contra pairs and Hamilton weights
- Decompositions and reductions of snarks
- Double covers of cubic graphs with oddness 4
- Even cycle decompositions of 4-regular graphs and line graphs
- Face colorings of embedded graphs
- Fast generation of cubic graphs
- Five cycle double covers of some cubic graphs
- Generation of cubic graphs
- Graphs with the Circuit Cover Property
- House of Graphs: a database of interesting graphs
- Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
- Measures of edge-uncolorability
- On Graphic-Minimal Spaces
- On cycle-double covers of graphs of small oddness
- On semiextensions and circuit double covers
- On stable cycles and cycle double covers of graphs with large circumference
- On the Imbedding of Linear Graphs in Surfaces
- On the total coloring of certain graphs
- Polyhedral decompositions of cubic graphs
- Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
- Reducible configurations for the cycle double cover conjecture
- Removable circuits in multigraphs
- Search for minimal trivalent cycle permutation graphs with girth nine
- Snarks and reducibility
- Special classes of snarks
- Stable dominating circuits in snarks
- The equivalence of two conjectures of Berge and Fulkerson
- Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
Cited in
(67)- Permutation snarks of order \(2 \pmod{8}\)
- Deciding whether four perfect matchings can cover the edges of a snark is NP-complete
- Some snarks are worse than others
- The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
- Strongly even cycle decomposable non-planar line graphs
- Square Coloring Planar Graphs with Automatic Discharging
- Berge–Fulkerson coloring for C(12)‐linked permutation graphs
- A note on \(\bar{X}\)-coloring and \(\hat{A}\)-coloring 4-regular graphs
- Rotationally symmetric snarks from voltage graphs
- K2‐Hamiltonian graphs: II
- Cubic graphs with colouring defect 3
- How many conjectures can you stand? A survey
- Snarks with resistance \(n\) and flow resistance \(2n\)
- Computational results and new bounds for the circular flow number of snarks
- Snarks with special spanning trees
- On 4-connected 4-regular graphs without even cycle decompositions
- Cubic graphs that cannot be covered with four perfect matchings
- Cycle double covers in cubic graphs having special structures
- Strongly even cycle decomposable 4-regular line graphs
- Construction of permutation snarks
- The smallest nontrivial snarks of oddness 4
- 1-factor and cycle covers of cubic graphs
- Odd 2-factored snarks
- Perfect matching index versus circular flow number of a cubic graph
- Berge-Fulkerson coloring for some families of superposition snarks
- On snarks that are far from being 3-edge colorable
- Snarks from a Kászonyi perspective: a survey
- Integer sequence discovery from small graphs
- Partially normal 5-edge-colorings of cubic graphs
- Snarks with large oddness and small number of vertices
- Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction
- On \(S\)-packing edge-colorings of cubic graphs
- Cycle double covers of infinite planar graphs
- Strong circuit double cover of some cubic graphs
- On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
- On stable cycles and cycle double covers of graphs with large circumference
- Superposition of snarks revisited
- On even cycle decompositions of line graphs of cubic graphs
- Morphology of small snarks
- On even cycle decompositions of 4-regular line graphs
- Weak oddness as an approximation of oddness and resistance in cubic graphs
- On type 2 snarks and dot products
- Small snarks with large oddness
- Some infinite classes of asymmetric nearly Hamiltonian snarks
- Classification and characterizations of snarks
- On perfect matching coverings and even subgraph coverings
- Uniquely edge-3-colorable graphs and snarks
- Circuit double covers of graphs
- A unified approach to construct snarks with circular flow number 5
- Cubic Cayley graphs and snarks
- Improved bounds for hypo-Hamiltonian graphs
- Generation of cubic graphs and snarks with large girth
- Cubic graphs with large circumference deficit
- Cycle double covers and non-separating cycles
- Structural and computational results on platypus graphs
- A faster test for 4-flow-criticality in snarks
- Snark designs
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- Measures of edge-uncolorability of cubic graphs
- Berge-Fulkerson conjecture on certain snarks
- Cubic graphs with no short cycle covers
- Switching 3-edge-colorings of cubic graphs
- On the smallest snarks with oddness 4 and connectivity 2
- House of graphs 2.0: a database of interesting graphs and more
- Critical and flow-critical snarks coincide
- A counterexample to the pseudo 2-factor isomorphic graph conjecture
- Treelike snarks
This page was built for publication: Generation and properties of snarks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463288)
