Generation and properties of snarks

DOI10.1016/j.jctb.2013.05.001zbMath1301.05119arXiv1206.6690OpenAlexW3098173695MaRDI QIDQ463288

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)

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

zbMATH Keywords

snarkscycle double coverscomputer generationshortest cycle covers

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Snarks with resistance \(n\) and flow resistance \(2n\) ⋮ On snarks that are far from being 3-edge colorable ⋮ Switching 3-edge-colorings of cubic graphs ⋮ On 4-connected 4-regular graphs without even cycle decompositions ⋮ A faster test for 4-flow-criticality in snarks ⋮ Cubic Graphs with Large Circumference Deficit ⋮ On Perfect Matching Coverings and Even Subgraph Coverings ⋮ On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings ⋮ Cycle Double Covers in Cubic Graphs having Special Structures ⋮ Construction of permutation snarks ⋮ Structural and computational results on platypus graphs ⋮ Strongly even cycle decomposable 4-regular line graphs ⋮ Strong Circuit Double Cover of Some Cubic Graphs ⋮ On even cycle decompositions of 4-regular line graphs ⋮ On type 2 snarks and dot products ⋮ On even cycle decompositions of line graphs of cubic graphs ⋮ A unified approach to construct snarks with circular flow number 5 ⋮ Berge–Fulkerson coloring for C(12)‐linked permutation graphs ⋮ On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs ⋮ Cubic graphs with colouring defect 3 ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ Deciding whether four perfect matchings can cover the edges of a snark is NP-complete ⋮ Some snarks are worse than others ⋮ Rotationally symmetric snarks from voltage graphs ⋮ K₂‐Hamiltonian graphs: II ⋮ Strongly even cycle decomposable non-planar line graphs ⋮ Improved bounds for hypohamiltonian graphs ⋮ Integer sequence discovery from small graphs ⋮ On stable cycles and cycle double covers of graphs with large circumference ⋮ Odd 2-factored snarks ⋮ How many conjectures can you stand? A survey ⋮ Superposition of snarks revisited ⋮ Critical and flow-critical snarks coincide ⋮ Snarks with special spanning trees ⋮ On \(S\)-packing edge-colorings of cubic graphs ⋮ Measures of edge-uncolorability of cubic graphs ⋮ Cubic Graphs with No Short Cycle Covers ⋮ Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction ⋮ Weak oddness as an approximation of oddness and resistance in cubic graphs ⋮ On the smallest snarks with oddness 4 and connectivity 2 ⋮ Snarks with large oddness and small number of vertices ⋮ Small snarks with large oddness ⋮ Cycle double covers of infinite planar graphs ⋮ Treelike snarks ⋮ Berge-Fulkerson coloring for some families of superposition snarks ⋮ Partially normal 5-edge-colorings of cubic graphs ⋮ Cubic graphs that cannot be covered with four perfect matchings ⋮ Berge-Fulkerson conjecture on certain snarks ⋮ The smallest nontrivial snarks of oddness 4 ⋮ Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 ⋮ 1‐Factor and Cycle Covers of Cubic Graphs ⋮ Cycle double covers and non-separating cycles ⋮ Perfect Matching Index versus Circular Flow Number of a Cubic Graph ⋮ Computational results and new bounds for the circular flow number of snarks ⋮ Circuit Double Covers of Graphs ⋮ House of graphs 2.0: a database of interesting graphs and more ⋮ Morphology of small snarks ⋮ Snarks from a Kászonyi perspective: a survey ⋮ A counterexample to the pseudo 2-factor isomorphic graph conjecture

Uses Software

• House of Graphs
• snarkhunter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On stable cycles and cycle double covers of graphs with large circumference
• Even cycle decompositions of 4-regular graphs and line graphs
• Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
• Measures of edge-uncolorability
• On semiextensions and circuit double covers
• Cycle covers (I) - minimal contra pairs and Hamilton weights
• Circle graphs and the cycle double cover conjecture
• A note on semiextensions of stable circuits
• Circuit double covers in special types of cubic graphs
• Search for minimal trivalent cycle permutation graphs with girth nine
• Removable circuits in multigraphs
• House of Graphs: a database of interesting graphs
• Double covers of cubic graphs with oddness 4
• Special classes of snarks
• A note about the dominating circuit conjecture
• Five cycle double covers of some cubic graphs
• Reducible configurations for the cycle double cover conjecture
• On the total coloring of certain graphs
• The equivalence of two conjectures of Berge and Fulkerson
• Face colorings of embedded graphs
• Covering Multigraphs by Simple Circuits
• On Graphic-Minimal Spaces
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• A survey on snarks and new results: Products, reducibility and a computer search
• Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
• Graphs with the Circuit Cover Property
• Decompositions and reductions of snarks
• Fast generation of cubic graphs
• The Generation of Fullerenes
• Compatible circuit decompositions of 4‐regular graphs
• Polyhedral decompositions of cubic graphs
• Blocking and anti-blocking pairs of polyhedra
• On the Imbedding of Linear Graphs in Surfaces
• On cycle-double covers of graphs of small oddness
• Stable dominating circuits in snarks