Snark (graph theory)
|
|
In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to four.
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.
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.
The well-known four color theorem is equivalent to the statement that no snark is planar.
The four flow conjecture of Bill Tutte in the case of cubic graphs states that every snark contains the Petersen graph as a minor.
List of snarks
- Petersen graph (10 vertices; 1891)
- 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)