The term "snark" was first popularized by Gardner (1976) as a class of minimal cubic graphs with edge
chromatic number 4 and certain connectivity requirements. (By Vizing's
theorem, the edge chromatic number of
every cubic graph is either three or four, so a snark
corresponds to the special case of four.) Snarks are therefore class
2 graphs. There are several definitions of snarks. Following Brinkmann et
al. (2013), call a weak snark a cyclically 4-edge
connected cubic graph with edge chromatic number
4 and girth at least 4, and a (generic, unqualified, or
strong) snark is a cyclically 4-edge connected cubic graph with edge
chromatic number 4 and girth at least 5 (Holton and
Sheehan 1993, p. 87, Brinkmann et al. 2013).
The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graphgraph minors. This conjecture was proven in 2001 by Robertson,
Sanders, Seymour, and Thomas, using an extension of the methods they used to reprove
the four-color theorem. All snarks are necessarily
nonplanar and nonhamiltonian.
The Petersen graph remained the only known snark until 1946, when the Blanuša snarks were
published (Blanuša 1946). Tutte discovered the next snark, which was rediscovered
together with a number of related snarks by Blanche Descartes. Szekeres (1973) found
a fifth snark, Isaacs (1975) proved there was an infinite family of snarks, and Martin
Gardner (1976) proposed that the name "snarks" be given to these graphs.
Of the smaller snarks, there is one with 10 vertices (the Petersen
graph), two with 18 vertices (the Blanuša
snarks), six with 20 vertices (of which one is the flower
snark), and 20 with 22 vertices.
The numbers of snarks on ,
12, 14, ... nodes are 1, 0, 0, 0, 2, 6, 20, 38, 280, 2900, 28399, 293059, 3833587,
60167732, ... (OEIS A130315; Brinkmann and
Steffen 1998).
The double star snark has 30 vertices, and the Szekeres snark has 50 vertices. Goldberg found
an additional class of snarks (the Goldberg snarks.
Additional snarks include the two Celmins-Swart
snarks on 26 vertices (Read and Wilson 1998, p. 281), the first and second
Loupekine snarks on 22 vertices (Read and Wilson
1998, p. 279) and the Watkins snark on 50 vertices
(Read and Wilson 1998, p. 281). Note that the flower
snarks, , ,
and are illustrated incorrectly by
Read and Wilson (1998, pp. 276 and 281-282).
The following table summarizes some named snarks, illustrated above.
Blanusa, D. "Problem cetiriju boja." Glasnik Mat. Fiz. Astr. Ser. II.1, 31-42, 1946.Brinkmann, G. and
Steffen, F. "Snarks and Reducibility." Ars Combin.50, 292-296,
1998.Brinkmann, G.; Goedgebeur, J.; Hägglund, J.; and Markström,
K. "Generation and Properties of Snarks." J. Comb. Th.103,
468-488, 2013.Cameron, P. J.; Chetwynd, A. G.; and Watkins,
J. J. "Decomposition of Snarks." J. Graph Th.11, 13-19,
1987.Chetwynd, A. G. and Wilson, R. J. "Snarks and Supersnarks."
In The Theory and Applications of Graphs (Ed. Y. Alavi et al. ).
New York: Wiley, pp. 215-241, 1981.Descartes, B. "Network-Colourings."
Math. Gaz.32, 67-69, 1948.Fiorini, S. "Hypohamiltonian
Snarks." In Graphs and Other Combinatorial Topics (Ed. M. Fiedler).
Leipzig, Germany: Teubner, 1983.Gardner, M. "Mathematical Games:
Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem."
Sci. Amer.234, No. 4, 126-130, 1976.Goldberg, M. K.
"Construction of Class 2 Graphs with Maximum Vertex Degree 3." J. Combin.
Th. Ser. B31, 282-291, 1981.Hägglund, J. and Markström,
K. "On Stable Cycles and Cycle Double Covers of Graphs with Large Circumference."
Disc. Math.312, 2540-2544, 2012.Holton, D. A. and
Sheehan, J. "Snarks." Ch. 3 in The
Petersen Graph. Cambridge, England: Cambridge University Press, pp. 79-111,
1993.House of Graphs. "Snarks." https://hog.grinvin.org/Snarks#snarks.Isaacs,
R. "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable."
Amer. Math. Monthly82, 221-239, 1975.Nedela, R. and Skoviera,
M. "Decompositions and Reductions of Snarks." J. Graph Th.22,
253-279, 1983.Read, R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and
276-281, 1998.Royle, G. "Snarks." http://people.csse.uwa.edu.au/gordon/remote/cubics/#snarks.Sloane,
N. J. A. Sequence A130315 in "The
On-Line Encyclopedia of Integer Sequences."Steffen, E. "Classification
and Characterisations of Snarks." SFB-Preprint 94-056. Bielefeld, Germany: Universität
Bielefeld, 1994.Szekeres, G. "Polyhedral Decompositions of Cubic
Graphs." Bull. Austral. Math. Soc.8, 367-387, 1973.Watkins,
J. J. "Snarks." Ann. New York Acad. Sci.576, 606-622,
1989.West, D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 304-306,
2000.
), and 20 with 22 vertices.
,
12, 14, ... nodes are 1, 0, 0, 0, 2, 6, 20, 38, 280, 2900, 28399, 293059, 3833587,
60167732, ... (OEIS A130315; Brinkmann and
Steffen 1998).
, 
, 
,
and 
are illustrated incorrectly by
Read and Wilson (1998, pp. 276 and 281-282).
