Inhaltsverzeichnis

1.  Einleitung  1

2.  Bestimmung chromatischer Polynome.  4

3.  Eigenschaften chromatischer Polynome  16

4.  Interpretation der Koeffizienten  20

5.  Chromatische Äquivalenz und chromatische Eindeutigkeit  28

6.  Schluss.  38

II

1. Einleitung

Das Konzept der „chromatischen Polynome“ wurde im Jahr 1912 von George D. Birkhoff

eingeführt ¹ und anschließend von ihm und Hassler Whitney weiterentwickelt, ² um die

bereits in den 1850er Jahren aufgestellte „Vierfarbenvermutung“ zu beweisen. Die

„Vierfarbenvermutung“ besagt, dass stets vier Farben ausreichen, um eine ebene Landkarte

derart einzufärben, dass keinen zwei angrenzenden Ländern die gleiche Farbe zugeordnet

wird. Zu einem Gegenstand der Graphentheorie wurde diese Vermutung, da sich das

Problem der Färbung einer Landkarte sehr leicht in das Problem der Färbung eines

Graphen übersetzen lässt. Viele Mathematiker des 19. und 20. Jahrhunderts scheiterten an

dem Versuch, die „Vierfarbenvermutung“ zu beweisen oder zu widerlegen. ³ Birkhoff und

Whitney probierten schließlich einen neuen Ansatz, indem sie einer jeden Landkarte (bzw.

einem jeden Graphen) ein „chromatisches Polynom“ zuordneten, das die möglichen

Färbungen mit einer bestimmten Anzahl an Farben zählte. Sie hofften, dass sich das

Problem dann mit den Methoden der reellen und komplexen Analysis lösen ließe. Dieser

Versuch misslang jedoch und der „Vierfarbensatz“ wurde erst im Jahr 1976 durch Kenneth

Appel, Wolfgang Haken und John Koch unter Zuhilfenahme moderner Computertechnik

und ohne Rückgriff auf das Konzept der „chromatischen Polynome“ bewiesen.

Im Jahr 1968 verfasste Ronald R. Read eine viel beachtete Einführung in die Theorie der

„chromatischen Polynome“ und ihre offenen Fragen, ⁴ die ein neuerliches Interesse an

diesem Gegenstand aufkommen ließ. Seitdem entwickelten sich die „chromatischen

Polynome“ zu einem der zentralen Gegenstände der algebraischen Graphentheorie. Read

warf unter anderem die Frage auf, wann zwei Graphen das gleiche „chromatische

Polynom“ zugeordnet wird. Diese Problemstellung wurde im Jahr 1978 von Chong-Yun

Chao und Earl Glenn Whitehead Jr. Aufgegriffen und verleitete sie dazu, das Konzept der

„chromatischen Äquivalenz“ einzuführen. 5

In der vorliegenden Arbeit sollen die Grundzüge der Theorie der „chromatischen

Polynome“ und des Konzeptes der „chromatischen Äquivalenz“ dargestellt werden. Zu

¹ Vgl. Birkhoff (1912)

² Vgl. Birkhoff (1930), Whitney (1932a) und Whitney (1932b)

³ Beispielhaft seien an dieser Stelle die vermeintlichen „Beweise“ von Alfred Kempe im Jahre 1879 und

Peter Guthrie Tait im Jahre 1880 erwähnt, die beide jeweils elf Jahre nach ihrer Veröffentlichung widerlegt

wurden.

⁴ Vgl. Read (1968)

⁵ Vgl. Chao/Whitehead (1978)

1

diesem Zweck werde ich in diesem ersten Kapitel zunächst einige grundlegende Begriffe

und Aussagen über Graphen und „Färbungen“ von Graphen aufgreifen, um im zweiten

Kapitel dieser Arbeit auf die konkrete Berechnung „chromatischer Polynome“ eingehen zu

können. Im Anschluss hieran werde ich im dritten und vierten Kapitel einige zentrale

Eigenschaften „chromatischer Polynome“ beweisen und im fünften Kapitel schließlich

eine Einführung in das von Chao und Whitehead entwickelte Konzept der „chromatischen

Äquivalenz“ geben. Am Ende der Arbeit werde ich die wichtigsten Ergebnisse dieser

Arbeit kurz zusammenfassen und auf einige noch offene Probleme verweisen.

Ein Graph ist ein Paar

Bezeichnung für die Menge der 2-elementigen Teilmengen von V ist. Die Elemente in V

∈ bezeichnen wir die heißen Knoten und die in E Kanten (von G). Für zwei Knoten , u v V

Kante { }

u v auch kurz mit uv und sagen, sie verbindet u und v, bzw. u und v sind die ,

∈ nennen wir benachbart bzw. inzident ∈ mit uv E Endknoten von uv. Zwei Knoten , u v V

(in G) und die Anzahl der zu einem Knoten benachbarten Knoten bezeichnen wir als

dessen Grad. Für die Knotenmenge eines Graphen G schreiben wir auch ( )

V G und für

seine Kantenmenge ( ) ( ) L = ∅ ∅ heißt leerer Graph. Im Folgenden sei V E . Der Graph ,

( ) = G V E , stets ein nicht leerer Graph.

Aus unserer obigen Definition von „Graph“ mittels ungeordneter Mengen folgt direkt, dass

wir ausschließlich „ungerichtete“ Graphen ohne „Mehrfachkanten“ oder

„Schlingen“ betrachten. Zudem werden in dieser Arbeit nur endliche Graphen behandelt,

d.h. Graphen mit endlicher Knoten- und damit auch Kantenmenge.

( ) ′ ′ ′ = G V E ein weiterer nicht leerer Graph. Wir bezeichnen G′ als , Im Folgenden sei

′ ⊆ ), falls V V ′ ⊆ und E E ′ ⊆ . Wir sagen in diesem Fall auch, Teilgraph von G (kurz: G G

′ = gilt, heißt G′ aufspannender Teilgraph dass G den Graphen G′ enthält. Falls sogar V V

von G.

ϕ ′ → Wir bezeichnen G als isomorph zu G′ , falls es eine Bijektion :V V gibt mit

( ) ( ) ϕ ϕ ′ ∈ ⇔ ∈ ∈ . Zueinander isomorphe Graphen haben unter uv E u v E u v V für alle ,

anderem immer gleich viele Knoten, gleich viele Kanten und gleich viele Knoten, die mit k

2

k ∈ ¥ . Weil sich die Knoten, Kanten und anderen Knoten benachbart sind für alle

0

Komponenten zueinander isomorpher Graphen miteinander identifizieren lassen

unterscheiden wir meist nicht zwischen solchen Graphen. Wir sprechen daher

beispielsweise von „dem vollständigen Graphen mit sechs Knoten“ und schreiben für zwei

= . Eine Menge zueinander isomorpher Graphen isomorphe Graphen G und G′ auch G G′

bezeichnen wir auch als Klasse (von Graphen).

→ Färbung (von G) und die Elemente der Menge S c V S Wir nennen eine Abbildung :

Farben, falls ( ) ( ) für je zwei benachbarte Ecken u und v von G. Für S λ ≠ = heißt c u c v

c auch λ -Färbung (von G). Ein Graph, für den eine λ -Färbung existiert, heißt λ -färbbar.

Wir heben an dieser Stelle hervor, dass eine Färbung nach dieser Definition nicht surjektiv

sein muss, bei einer λ -Färbung also nicht zwangsläufig alle Farben verwendet werden

λ λ λ -Färbung eines Graphen immer auch eine 1 λ - ≤ eine 2 müssen. Daher ist für 1

2

λ -färbbarer Graph insbesondere 2 λ -färbbar. Da wir den Begriff der Färbung und ein 1

Färbung nur für nicht leere Graphen definieren, gibt es aus unserer Perspektive keine „0-

färbbaren“ Graphen. Die kleinste Zahl λ ∈ ¥ , für die ein Graph G λ -färbbar ist, nennt

man seine chromatische Zahl ( ) χ G . Mit Hilfe der chromatischen Zahl lässt sich der

Vierfarbensatz auch folgendermaßen ausdrücken: Für einen planaren Graphen G gilt

( ) 4 χ ≤ . Ein planarer Graph ist ein Graph, der sich so in einer Ebene zeichnen lässt, G

dass sich seine Kanten nicht überschneiden. Die Berechnung chromatischer Zahlen ist ein

bedeutendes und mitunter sehr schwer lösbares Problem der Graphentheorie, soll aber kein

Schwerpunkt dieser Arbeit sein. Stattdessen wollen wir uns mit der Frage beschäftigen,

wie sich die Anzahl der „verschiedenen“ λ -Färbungen eines Graphen bestimmen lässt.

Zunächst einmal müssen wir hierzu allerdings klären werden, was wir unter

„verschiedenen“ Färbungen verstehen. Es drängen sich nämlich zwei Fragen auf. Erstens:

Betrachten wir mehrere Färbungen eines Graphen auch dann als unterschiedlich, wenn sie

durch zyklische Permutation der Knoten auseinander hervorgehen? Betrachten wir

beispielsweise die in der folgenden Abbildung dargestellten Färbungen des

Dreiecksgraphen D als gleich?

Wir wollen in dieser Arbeit Färbungen auch dann als verschieden betrachten, wenn sie

durch Permutation der Knoten auseinander vorgehen. Die beiden in der obigen Abbildung

dargestellten Färbungen betrachten wir daher als verschieden. Zweitens: Spielt es eine

Rolle, mit welchen Farben ein Graph konkret eingefärbt wird? Man könnte zwei

Färbungen eines Graphen als äquivalent ansehen, falls sie auseinander lediglich durch

Permutation der Farben hervorgehen, wie in dem folgenden Beispielgraphen D′ :

Wir nehmen auch diesen Blickwinkel nicht ein und betrachten zwei Färbungen auch dann

als unterschiedlich, wenn sie durch Permutation auseinander hervorgehen. Nachdem wir

nun festgelegt haben, was wir unter verschiedenen Färbungen verstehen, wollen wir uns

nun der Frage zuwenden, wie wir diese zählen können.

Die Anzahl der verschiedenen λ -Färbungen eines nicht leeren Graphen G mit λ ∈ ¥

bezeichnen wir mit ( ) P G λ . Für festes G und variables λ nennen wir die Funktion |

→ P ¥ vorerst die chromatische Funktion (von G). Da es beispielsweise sechs 3: ¥

Färbungen des obigen Dreiecksgraphen D gibt, gilt ( ) P D λ = . | 6

λ -Aus der obigen Definition folgt offensichtlich direkt, dass ein Graph genau dann 0

färbbar ist, wenn ( ) P G λ > gilt. Zudem ist die chromatische Zahl ( ) χ G | 0 eines

0

λ ∈ ¥ mit ( ) P G λ > und der Vierfarbensatz besagt, dass | 0 Graphen G die kleinste Zahl 0

0

( ) ≠ für alle planaren Graphen G gilt. Wir halten außerdem fest, dass zwei P G | 4 0

isomorphe Graphen die gleiche chromatische Funktion haben, da sich ihre Knoten und

Kanten wie bereits angesprochen miteinander identifizieren lassen.

2. Bestimmung chromatischer Polynome

In diesem Kapitel wollen wir uns der konkreten Berechnung chromatischer Funktionen

zuwenden. Bevor wir allerdings allgemeine Rechenformeln aufstellen, wollen wir die

chromatischen Funktionen zweier einfacher Klassen von Graphen bestimmen.

4

Ein nicht leerer Graph G heißt kantenlos, falls E(G)= ∅ . Hat ein solcher Graph n Knoten,

n ≥ Knoten, in dem je so bezeichnen wir ihn mit n E . Einen nicht leeren Graphen mit 2

zwei Knoten benachbart sind, nennen wir vollständig und bezeichnen ihn mit n K . Auch

einen Graphen mit nur einem Knoten betrachten wir als vollständig. Die Anzahl m der

Kanten eines vollständigen Graphen mit n Knoten entspricht der Anzahl der Möglichkeiten,

zwei seiner n Knoten auszuwählen, um diese durch eine Kante zu verbinden:

Die folgende Abbildung zeigt den kantenlosen und den vollständigen Graphen mit jeweils

vier Knoten:

E hat die chromatische Funktion ( ) P E λ λ = . Theorem 1. Der kantenlose Graph n n n |

Beweis. Färben wir einen beliebigen Knoten von n E , so hat dies keinerlei Auswirkungen

auf die Anzahl der Farben, die uns für die verbleibenden Knoten zur Verfügung stehen,

weil die Knoten von n E paarweise nicht benachbart sind. Für jeden der n Knoten stehen

uns daher alle λ Farben zur Verfügung und es gibt insgesamt ( ) P E λ λ = n n |

verschiedene Färbungen von n E . W

Theorem 2. Der vollständige Graph n K hat die chromatische Funktion

K mit einer der λ Farben, so stehen uns Beweis. Färben wir einen beliebigen Knoten von n

λ − Farben zur Verfügung, da dieser Knoten n − Knoten noch für die verbleibenden 1 1

mit jedem anderen benachbart ist und keinem seiner Nachbarn die gleiche Farbe

zugeordnet werden kann. Entsprechend stehen uns nach der Färbung eines weiteren

λ − Farben zur Verfügung, da auch dieser mit allen anderen benachbart ist. Knotens noch 2

Fahren wir auf diese Weise fort und färben alle n Knoten, so folgt:

5

Wir halten an dieser Stelle schon einmal fest, dass die chromatischen Polynome von

kantenlosen und vollständigen Graphen Polynome sind. Da kantenlose und vollständige

Graphen sehr einfache Strukturen haben, konnten wir ihre chromatischen Polynome relativ

leicht bestimmen. Wollen wir aber die chromatischen Funktionen beliebig komplexer

Graphen bestimmen, so stellt uns dies vor ein nicht unerhebliches Problem. Im Folgenden

soll daher ein Verfahren erläutert werden, welches die systematische Berechnung der

chromatischen Funktionen beliebiger Graphen ermöglicht.

( ) = . Dann definieren wir: = ∈ und e uv G V E u v V , Sei ein nicht leerer Graph, ,

( ) ( ) { } { } − = + = ∪ G e V E e G e V E e : , \ , : ,

( ) ′ ′ = G e V E \ : , und mit

( ) { } { } ′ = ∪ V V u v v : \ , und

e

{ } { } { } { } { } ′ = ∈ ∈ ∈ ∩ =∅ ∪{ }. v y uy E e vy E e E xy E x y u v : \ \ : : , , oder

e

G e nennen wir auch die Kantenkontraktion von e in G. Anschaulich Den Graphen \

− und G e + also, indem wir zwischen zwei Knoten u und v erhalten wir die Graphen G e

G e zu erhalten, müssen wir eine Kante e hinzufügen bzw. entfernen. Um den Graphen \

die Kante e solange „zusammenziehen“ (kontrahieren), bis ihre Endknoten u und v

v bilden, mit dem alle bisherigen „übereinander liegen“ und einen neuen Knoten e

Nachbarn von u oder v benachbart sind. Die folgende Abbildung zeigt ein Beispiel:

− genau eine Kante weniger hat als G und Wir heben an dieser Stelle hervor, dass G e

G e sogar mindestens eine Kante weniger. Diese Erkenntnis wird uns später noch von \

großem Nutzen sein. Wir können nun ein fundamentales Theorem formulieren, welches zu

einem Verfahren führt, das die Berechnung der chromatischen Funktionen beliebiger

Graphen ermöglicht:

6

( ) Theorem 3 (Reduktionsformel). ⁶ Sei G V E , ein Graph mit mindestens einer Kante.

∈ : Dann gilt für alle e E

( ) ( ) ( ) λ λ λ = − − P G P G e P G e | | \ | .

Beweis. Sei G ein Graph und e eine seiner Kanten mit Endknoten u und v. Wir zählen die

− und unterscheiden zu diesem Zweck zwei Fälle. Färbungen des Graphen G e

− Fall 1: Die Knoten u und v werden gleich gefärbt. In diesem Fall lässt sich G e

G e , es gilt also offensichtlich auf genau so viele Arten einfärben, wie \

( ) ( ) λ λ − = P G e P G e | \ | .

Fall 2: Die Knoten u und v werden unterschiedlich gefärbt. In diesem Fall lässt sich jede

− mit einer Färbung von G identifizieren, da die in G benachbarten Färbung von G e

Ecken u und v ja verschieden eingefärbt werden müssen. In diesem Fall gilt daher

( ) ( ) λ λ − = P G e P G | | .

( ) ( ) ( ) λ λ λ − = + P G e P G e P G | \ | | und mittels Insgesamt folgt also

Äquivalenzumformung die Behauptung. W

Um die Reduktionsformel anwenden und hierbei Lesbarkeit garantieren zu können, wollen

wir zunächst eine Notation vereinbaren: Eine graphische Darstellung eines Graphen G

steht im Folgenden auch für seine chromatische Funktion in der Variablen λ . Statt also

beispielsweise ( ) ( ) ( ) λ λ λ = − − P G P G e P G e | | \ | zu schreiben und erläutern zu müssen,

− und \ wie die Graphen G, G e G e genau aussehen, schreiben wir auch einfach

Diese äußerst nützliche Notation wurde ursprünglich von Zykov ⁷ eingeführt, aber

beispielsweise auch von Read verwendet. 8

Mit der Reduktionsformel lässt sich, die chromatische Funktion eines Graphen G als

− und \ Differenz der chromatischen Funktionen zweier Graphen G e G e , die - wie oben

gesehen - mindestens eine Kante weniger als G haben, darstellen. Diese Erkenntnis

können wir nutzen, um die chromatischen Funktionen beliebiger Graphen G mit m Kanten

zu berechnen. Wenden wir die Reduktionsformel in einem ersten Schritt auf G an, so

⁶ Vgl. Whitney (1932a)

⁷ Vgl. Zykov (1952)

⁸ Vgl. Read (1968)

7