Snark (graph theory)

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 vertex has three neighbors, and the edges cannot be colored by three colors without two edges of the same color meeting at a point.

History

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.

Properties

All snarks are non-Hamiltonian, and many known snarks are hypohamiltonian: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be "bicritical": the removal of any two vertices leaves a 3-edge-colorable subgraph (Steffen 1998, 2001).

nark theorem

W. T. Tutte conjectured that every snark has the Petersen graph as a minor. That is, he conjectured that the smallest snark, the Petersen graph, may be formed from any other snark by contracting some edges and deleting others. Equivalently (because the Petersen graph has maximum degree three) every snark has a subgraph that can be formed from the Petersen graph by subdividing some of its edges. This conjecture is a strengthened form of the four color theorem, because any graph containing the Petersen graph as a minor must be nonplanar. In 2001, Robertson, Sanders, Seymour, and Thomas announced a proof of this conjecture, and the result is now known as the snark theorem. [citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf.] See the Hadwiger conjecture for other problems and results relating graph coloring to graph minors.

Tutte also conjectured a generalization of the snark theorem to arbitrary graphs: every bridgeless graph with no Petersen minor has a nowhere zero 4-flow. That is, the edges of the graph may be assigned a direction, and a number from the set {1, 2, 3}, such that the sum of the incoming numbers minus the sum of the outgoing numbers at each vertex is divisible by four. As Tutte showed, for cubic graphs such an assignment exists if and only if the edges can be colored by three colors, so the conjecture follows from the snark theorem in this case. However, this conjecture remains open for graphs that need not be cubic. [ [http://garden.irmacs.sfu.ca/?q=op/4_flow_conjecture 4-flow conjecture] , Open Problem Garden.]

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)

Notes

References

*
*
*
*citation
last = Steffen | first = E.
title = Classification and characterizations of snarks
journal = Discrete Mathematics
volume = 188 | year = 1998 | issue = 1–3 | pages = 183–203
id = MathSciNet | id = 1630478
doi = 10.1016/S0012-365X(97)00255-0.
*citation
last = Steffen | first = E.
title = On bicritical snarks
journal = Math. Slovaca
volume = 51 | year = 2001 | issue = 2 | pages = 141–150
id = MathSciNet | id = 1841443.
*

External links

*
* Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). " [http://www.ijp.si/ftp/pub/preprints/ps/2004/pp914.ps Blanuša Double] ". "Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia".