Snark (Graphentheorie)

In der Graphentheorie ist ein Snark ein ungerichteter Graph mit genau drei Kanten pro Knoten, der nicht 3-Kanten-färbbar ist. Um triviale Fälle zu vermeiden, werden Snarks oft weiter in ihrem Zusammenhang und der Länge ihrer Kreise beschränkt.^[1]

Der Name Snark wurde 1976 von Martin Gardner geprägt und ist inspiriert von Lewis Carrolls Unsinnsgedicht The Hunting of the Snark.^[2] Allerdings wurde diese Klasse von Graphen schon lange vorher untersucht. Sie geht auf Peter Guthrie Tait zurück, der 1880 bewies, dass der Vier-Farben-Satz äquivalent ist zu der Aussage, dass kein Snark ein planarer Graph ist.^[3] Der erste Graph, für den bewiesen wurde, dass es sich um einen Snark handelt, ist der Petersen-Graph (Beweis 1898 durch Julius Peter Christian Petersen^[4]).

Neben ihrer Bedeutung für das Färbungsproblem sind Snarks auch mit anderen schwierigen Problemen der Graphentheorie verbunden. In einem Artikel aus dem Jahr 2010 heißt es:

„Bei der Untersuchung verschiedener wichtiger und schwieriger Probleme in der Graphentheorie (wie der cycle-double-cover-Vermutung und der 5-flow-Vermutung) stößt man auf eine interessante, aber etwas mysteriöse Sorte von Graphen, die Snarks genannt werden. Trotz ihrer einfachen Definition [...] und einer mehr als hundert Jahre andauernden Untersuchung sind ihre Eigenschaften und Struktur weitgehend unbekannt.“^[5]

Seit den 1970er Jahren ist bekannt, dass es unendlich viele Snarks gibt.^[6]

Weblinks

Commons: Snark – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

↑ Ed Pegg, Jr. et al., Wolfram MathWorld: Snark
↑ Martin Gardner: Snarks, boojums, and other conjectures related to the four-color-map theorem. In: Scientific American. Band 234, Nr. 4, 1976, S. 126–130, doi:10.1038/scientificamerican0476-126, JSTOR:24950334.
↑ Peter G. Tait: Remarks on the colourings of maps. In: Proceedings of the Royal Society of Edinburgh. Band 10, 1880, S. 729, doi:10.1017/S0370164600044643.
↑ Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).
↑ In the study of various important and difficult problems in graph theory (such as the cycle double cover conjecture and the 5-flow conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown. Siehe Miroslav Chladný, Martin Škoviera: Factorisation of snarks. In: Electronic Journal of Combinatorics. Band 17, 2010, S. R32, doi:10.37236/304.
↑ Sarah-Marie Belcastro: The continuing saga of snarks. In: The College Mathematics Journal. Band 43, Nr. 1, 2012, S. 82–87, doi:10.4169/college.math.j.43.1.082.

[Snark-1] Ed Pegg, Jr. et al., Wolfram MathWorld: Snark

[2] Martin Gardner: Snarks, boojums, and other conjectures related to the four-color-map theorem. In: Scientific American. Band 234, Nr. 4, 1976, S. 126–130, doi:10.1038/scientificamerican0476-126, JSTOR:24950334.

[tait-3] Peter G. Tait: Remarks on the colourings of maps. In: Proceedings of the Royal Society of Edinburgh. Band 10, 1880, S. 729, doi:10.1017/S0370164600044643.

[petersen-4] Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).

[5] In the study of various important and difficult problems in graph theory (such as the cycle double cover conjecture and the 5-flow conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown. Siehe Miroslav Chladný, Martin Škoviera: Factorisation of snarks. In: Electronic Journal of Combinatorics. Band 17, 2010, S. R32, doi:10.37236/304.

[belcastro-6] Sarah-Marie Belcastro: The continuing saga of snarks. In: The College Mathematics Journal. Band 43, Nr. 1, 2012, S. 82–87, doi:10.4169/college.math.j.43.1.082.

[1]

[2]

[3]

[4]

[5]

[6]