×

Snarks and reducibility. (English) Zbl 0963.05050

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'\).
The 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite