Generation and properties of snarks
From MaRDI portal
Publication:463288
DOI10.1016/J.JCTB.2013.05.001zbMATH Open1301.05119arXiv1206.6690OpenAlexW3098173695MaRDI QIDQ463288FDOQ463288
Klas Markström, Jan Goedgebeur, Gunnar Brinkmann, Jonas Hägglund
Publication date: 16 October 2014
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1206.6690
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)
Cites Work
- House of Graphs: a database of interesting graphs
- The Generation of Fullerenes
- On the total coloring of certain graphs
- Title not available (Why is that?)
- Decompositions and reductions of snarks
- Double covers of cubic graphs with oddness 4
- Five cycle double covers of some cubic graphs
- The equivalence of two conjectures of Berge and Fulkerson
- Title not available (Why is that?)
- Title not available (Why is that?)
- Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
- Polyhedral decompositions of cubic graphs
- Blocking and anti-blocking pairs of polyhedra
- On cycle-double covers of graphs of small oddness
- Removable circuits in multigraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graphs with the Circuit Cover Property
- Title not available (Why is that?)
- Compatible circuit decompositions of 4‐regular graphs
- Cycle covers (I) - minimal contra pairs and Hamilton weights
- On the Imbedding of Linear Graphs in Surfaces
- Covering Multigraphs by Simple Circuits
- Special classes of snarks
- Title not available (Why is that?)
- On Graphic-Minimal Spaces
- Even cycle decompositions of 4-regular graphs and line graphs
- A note on semiextensions of stable circuits
- Circuit double covers in special types of cubic graphs
- Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
- Stable dominating circuits in snarks
- On semiextensions and circuit double covers
- Fast generation of cubic graphs
- Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
- Circle graphs and the cycle double cover conjecture
- Reducible configurations for the cycle double cover conjecture
- On stable cycles and cycle double covers of graphs with large circumference
- Title not available (Why is that?)
- Search for minimal trivalent cycle permutation graphs with girth nine
- A note about the dominating circuit conjecture
- Snarks and reducibility
- Face colorings of embedded graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A survey on snarks and new results: Products, reducibility and a computer search
- Title not available (Why is that?)
- Measures of edge-uncolorability
Cited In (63)
- How many conjectures can you stand? A survey
- Snarks with special spanning trees
- Morphology of small snarks
- Superposition of snarks revisited
- Weak oddness as an approximation of oddness and resistance in cubic graphs
- On snarks that are far from being 3-edge colorable
- Small snarks with large oddness
- On the smallest snarks with oddness 4 and connectivity 2
- Odd 2-factored snarks
- Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction
- Berge-Fulkerson conjecture on certain snarks
- On stable cycles and cycle double covers of graphs with large circumference
- On 4-connected 4-regular graphs without even cycle decompositions
- Perfect Matching Index versus Circular Flow Number of a Cubic Graph
- On even cycle decompositions of line graphs of cubic graphs
- On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
- Cycle double covers of infinite planar graphs
- On Perfect Matching Coverings and Even Subgraph Coverings
- Berge-Fulkerson coloring for some families of superposition snarks
- Classification and characterizations of snarks
- Uniquely edge-3-colorable graphs and snarks
- Improved bounds for hypohamiltonian graphs
- A faster test for 4-flow-criticality in snarks
- Measures of edge-uncolorability of cubic graphs
- Cubic graphs that cannot be covered with four perfect matchings
- Strongly even cycle decomposable 4-regular line graphs
- Cycle double covers and non-separating cycles
- Switching 3-edge-colorings of cubic graphs
- Cycle double covers in cubic graphs having special structures
- On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings
- A counterexample to the pseudo 2-factor isomorphic graph conjecture
- Computational results and new bounds for the circular flow number of snarks
- Partially normal 5-edge-colorings of cubic graphs
- On \(S\)-packing edge-colorings of cubic graphs
- A unified approach to construct snarks with circular flow number 5
- Construction of permutation snarks
- The smallest nontrivial snarks of oddness 4
- Cubic Graphs with Large Circumference Deficit
- Integer sequence discovery from small graphs
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- 1‐Factor and Cycle Covers of Cubic Graphs
- Snarks with large oddness and small number of vertices
- Circuit Double Covers of Graphs
- Structural and computational results on platypus graphs
- On type 2 snarks and dot products
- On even cycle decompositions of 4-regular line graphs
- Snarks with resistance \(n\) and flow resistance \(2n\)
- Critical and flow-critical snarks coincide
- Treelike snarks
- Cubic Graphs with No Short Cycle Covers
- Snarks from a Kászonyi perspective: a survey
- Strong Circuit Double Cover of Some Cubic Graphs
- House of graphs 2.0: a database of interesting graphs and more
- Square Coloring Planar Graphs with Automatic Discharging
- Deciding whether four perfect matchings can cover the edges of a snark is NP-complete
- Berge–Fulkerson coloring for C(12)‐linked permutation graphs
- Some snarks are worse than others
- Permutation snarks of order \(2 \pmod{8}\)
- Rotationally symmetric snarks from voltage graphs
- K2‐Hamiltonian graphs: II
- Strongly even cycle decomposable non-planar line graphs
- A note on \(\bar{X}\)-coloring and \(\hat{A}\)-coloring 4-regular graphs
- Cubic graphs with colouring defect 3
Uses Software
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)
