Petersen-Graph

Petersen-Graph
Benannt nach Julius Peter Christian Petersen
Größe 10 Knoten, 15 Kanten
Eigenschaftensnark, kubisch.
Chromatische Zahl3
Chromatischer Index4
Knotenzusammenhang3
Cliquenzahl2
Schnittzahl2
Chromatisches Polynomt(t−1)(t−2)(t7−12t6+67t5−
230t4+529t3−814t2+775t−352)
Charakteristisches Polynom(t−1)5(t+2)4(t−3)
LCF-Notation{{{LCF}}}

Der Petersen-Graph (benannt nach dem dänischen Mathematiker Julius Petersen) ist ein 3-regulärer (also kubischer) Graph mit 10 Knoten. Das bedeutet, dass jeder der Knoten drei Nachbarn hat, die Gradfolge ist also (3,3,3,3,3,3,3,3,3,3). Der Petersen-Graph ist in der Graphentheorie ein oft verwendetes Beispiel und Gegenbeispiel. Er tritt auch in der tropischen Geometrie auf.

Eigenschaften des Petersen-Graphen:

Färbung

Eine optimale Kantenfärbung des Petersen-Graphen.
Eine optimale Knotenfärbung des Petersen-Graphen.

Der Petersen-Graph hat eine chromatische Zahl von 3, d. h. die Knoten müssen mit mindestens 3 Farben gefärbt werden, sodass jeweils zwei benachbarte Knoten unterschiedliche Farben haben. Der chromatische Index ist 4, d. h. man benötigt mindestens 4 Farben um alle Kanten so einzufärben, dass die inzidente Kanten jedes Knoten paarweise verschiedene Farben haben. Da der Petersen-Graph brückenlos und kubisch ist, aber einen chromatischen Index von 4 besitzt, zählt der Petersen-Graph zu den sogenannten Snark-Graphen. Er ist der kleinste und von 1898 bis 1946 der einzige Graph, für den diese Eigenschaft nachgewiesen wurde.

Commons: Petersen-Graph – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

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