TOPICS
Search

Snark


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 graph graph 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 J_5), and 20 with 22 vertices.

The numbers of snarks on n=10, 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 J_5, J_7, J_9, and J_(11) are illustrated incorrectly by Read and Wilson (1998, pp. 276 and 281-282).

Snarks

The following table summarizes some named snarks, illustrated above.


See also

Almost Hamiltonian Graph, Almost Hypohamiltonian Graph, Blanuša Snarks, Celmins-Swart Snarks, Class 2 Graph, Cubic Graph, Cyclic Edge Connectivity, Descartes Snarks, Double Star Snark, Edge Chromatic Number, Flower Snark, Goldberg Snark, Nonhamiltonian Graph, Petersen Graph, Szekeres Snark, Vizing's Theorem, Watkins Snark, Weak Snark

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

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. B 31, 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. Monthly 82, 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.

Cite this as:

Pegg, Ed Jr. and Weisstein, Eric W. "Snark." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Snark.html

Subject classifications