Lexikon der Mathematik: Petersen-Graph
der skizzierte kubische GraphP.
Dieser berühmte, hochgradig symmetrische Graph von J. Petersen (1898) spielt in der Graphentheorie eine äußerst wichtige Rolle.
Beispielsweise besitzt der Petersen-Graph P keine 3-Kantenfärbung, womit für den chromatischen Index (Kantenfärbung) notwendig χ′ (P) = 4 gilt, daher ist P ein Klasse 2-Graph. Dies sieht man am einfachsten wie folgt ein: Man versuche eine 3-Kantenfärbung zu konstruieren, indem man zunächst den äußeren Kreis der Länge 5 färbt (dazu sind schon 3 Farben notwendig) und sich dann nach innen „vorarbeitet“. Zwangsläufig benötigt man dann eine weitere Farbe und erkennt auch, daß man mit vier Farben auskommt.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.