Snarks and reducibility

MaRDI QIDQ2713660zbMATH OpenFDO

Authors Gunnar Brinkmann, Eckhard Steffen

Publication date 10 June 2001

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

snarksvertex reducibility

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Review text

A snark is a simple, cyclically 4-edge connected cubic graph with girth at least 5 and chromatic index 4. A cubic graph \(G\) is vertex-reducible to a simple cubic graph \(G'\) if \(G'\) can be obtained from \(G\) by removing two vertices together with all incident edges from \(G\) and adding new edges to obtain \(G'\). NEWLINENEWLINENEWLINEThe complete list of all snarks of order less than 30 is given. Moreover, a brief survey of different reduction methods for snarks is presented. For all these reductions the complete numbers of irreducible snarks of order less than 30 and the number of nonisomorphic 3-critical subgraphs of these graphs is given.

Recommendations

• Decompositions and reductions of snarks
• scientific article; zbMATH DE number 867669
• Irreducible snarks of given order and cyclic connectivity
• A survey on snarks and new results: Products, reducibility and a computer search
• scientific article; zbMATH DE number 3884206

Cited in

(28)

• The construction and reduction of strong snarks
• Classification and characterizations of snarks
• 6-decomposition of snarks
• Measurements of edge-uncolorability
• Morphology of small snarks
• 3-critical subgraphs of snarks
• Superposition of snarks revisited
• Critical and flow-critical snarks coincide
• Some results on the structure of multipoles in the study of snarks
• Factorisation of snarks
• Irreducible snarks of given order and cyclic connectivity
• Berge-Fulkerson conjecture on certain snarks
• scientific article; zbMATH DE number 3884206 (Why is no real title available?)
• scientific article; zbMATH DE number 7228873 (Why is no real title available?)
• Exponentially many hypohamiltonian snarks
• Some Topics in Graph Theory
• A survey on snarks and new results: Products, reducibility and a computer search
• scientific article; zbMATH DE number 1011074 (Why is no real title available?)
• scientific article; zbMATH DE number 1737273 (Why is no real title available?)
• Generation and properties of snarks
• scientific article; zbMATH DE number 867669 (Why is no real title available?)
• Decompositions and reductions of snarks
• On the number of colorings of a snark minus an edge
• Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms
• Measures of edge-uncolorability of cubic graphs
• On double Roman domination problem for several graph classes
• Fano colourings of cubic graphs and the Fulkerson conjecture
• Improved edge-coloring with three colors

This page was built for publication: Snarks and reducibility

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