Snark (graph theory)
From Free net encyclopedia
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.
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)
References
External links
- Template:MathWorld
- Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). "Blanuša Double". Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.pl:Żmirłacz (teoria grafów)