Snark (graph theory)
From Wikipedia, the free encyclopedia
- This page is on an object in graph theory. For other uses of the word, see snark (disambiguation).
In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4.
In other words, it is a graph in which every node has three branches, and the edges cannot be colored in fewer than four colors without two edges of the same color meeting at a point.
P. G. Tait initiated the study of snarks in 1880, when he proved that the four color theorem is equivalent to the statement that no snark is planar. The first known snark was the Petersen graph, discovered in 1898. In 1946, Danilo Blanuša discovered two more snarks, and in 1975 Isaacs generalized Blanuša's method to construct an infinite family of snarks. Snarks were so named by the American mathematician Martin Gardner in 1976, after the mysterious and elusive object of the poem The Hunting of the Snark by Lewis Carroll.
In 2001, Robertson, Sanders, Seymour, and Thomas announced a proof of W. T. Tutte's conjecture that every snark has the Petersen graph as a minor.
[edit] List of snarks
- Petersen graph (10 vertices; 1898)
- Blanuša snarks (two with 18 vertices, discovered in 1946)
- Descartes' snark (discovered by Bill Tutte)
- Szekeres snark (50 vertices; 1973)
- flower snark (20 vertices)
- double star snark (30 vertices)
[edit] References
- Danilo Blanuša (1946). "Problem četiriju boja". Glasnik Mat. Fiz. Astr. Ser II 1: 31–42.
- Martin Gardner (1976). "Mathematical Games". Scientific American 4 (234): 126–130.
- R. Isaacs (1975). "Infinite families of non-trivial trivalent graphs which are not Tait-colorable". American Mathematical Monthly 82: 221–239.
- P. G. Tait (1880). "Remarks on the colourings of maps". Proc. R. Soc. Edinburgh 10: 729.
[edit] External links
- Weisstein, Eric W., Snark at MathWorld.
- Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). "Blanuša Double". Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.
