Snark (Graphentheorie)
# 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.

Der Name Snark wurde 1976 von Martin Gardner geprägt und ist inspiriert von Lewis Carrolls Unsinnsgedicht The Hunting of the Snark. 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. 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).

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.“

Seit den 1970er Jahren ist bekannt, dass es unendlich viele Snarks gibt.

