Graph/Färbungen/Chromatisches Polynom/Textabschnitt
Wir werden sehen, dass diese Funktion in der Tat ein Polynom ist, von daher wäre es korrekter, vorläufig von der chromatischen Funktion zu sprechen. Wenn man eine zulässige Färbung mit einer Permutation auf der Farbenmenge verknüpft, so erhält man wieder eine zulässige Färbung. Färbungen, die durch einen solchen Farbenwechsel auseinander hervorgehen, haben zwar die gleichen Eigenschaften, sie werden aber als verschiedene Färbungen gezählt, da ja eine Färbung als eine Abbildung definiert ist.
Es sei ein Graph mit Knotenpunkten und ohne Kanten. Dann ist das chromatische Polynom gleich . Es ist ja in diesem Fall jede Abbildung
eine zulässige Färbung und somit gibt es nach Fakt zulässige Färbungen mit (höchstens) Farben.
Es sei ein vollständiger Graph mit Knotenpunkten. Dann ist das chromatische Polynom gleich
Bei Farben gibt es keine zulässige Färbung des vollständigen Graphen. Bei sind nur die injektiven Abbildungen
zulässige Färbungen. Davon gibt es nach Fakt Stück.
Es sei ein Graph und sein chromatisches Polynom.
Dann ist die Anzahl der zulässigen Färbungen von mit genau Farben gleich
Wir betrachten zulässige Färbungen von mit der Farbenmenge . Die in Frage stehende Menge der zulässigen Färbungen mit genau Farben sind dabei die surjektiven Abbildungen. Zu sei die Menge der zulässigen Färbungen in , die nicht treffen. Zu einer Teilmenge ist die Menge der zulässigen Färbungen, die nur Farben aus verwenden. Mit der Siebformel ist
der Übergang zum Komplement ergibt die Behauptung.
Für das chromatische Polynom gelten die folgenden Aussagen.
- Die
chromatische Zahl
von ist die minimale Zahl
mit
- Mit
gelten die Abschätzungen
- Für
ist
Insbesondere ist das chromatische Polynom durch die Werte festgelegt.
(1) ist klar. (2). Die rechte Abschätzung ist klar, da rechts die Anzahl der Färbungen mit Farben überhaupt ohne Zulässigkeitsbedingung steht. Die linke Seite ist klar für . Für . ist die Zahl links nach Fakt die Anzahl der injektiven Abbildungen von nach , und diese sind stets zulässig. (3). Eine zulässige Färbung mit (höchstens) Farben ist eine zulässige Färbung mit genau Farben für ein . Es sei die Anzahl der zulässigen Färbungen mit genau Farben. Dann ist die Anzahl der zulässigen Färbungen mit Farben unter Verwendung von Fakt gleich
Das chromatische Polynom zu einem Graphen mit Knotenpunkten
ist ein normiertes Polynom vom Grad .
Für das chromatische Polynom
gelten die folgenden Eigenschaften.
- Es sei
eine Kante von mit dem zugehörigen
Kontraktionsgraphen
. Dann gilt
- Bei einer disjunkten Vereinigung von zwei Graphen
ist
(1). Sei . Wir zeigen
indem wir die zulässigen Färbungen analysieren. Eine zulässige Färbung von ist eine zulässige Färbung von , bei der auch die Bedingung erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von mit den zulässigen Färbungen von entsprechen. Über den surjektiven schwachen Graphhomomorphismus
erhält man aus einer zulässigen Färbung von direkt eine (nichtzulässige) Färbung von mit identischem Wert auf und und damit direkt eine zulässige Färbung auf mit identischem Wert auf und . Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung
mit gegeben ist, so kann man dies direkt als eine Färbung auf auffassen. Wenn eine Kante von ist, so liegt dieser Kante eine Kante in zugrunde, und daher überträgt sich die Zulässigkeit.
(2). Eine zulässige Färbung auf mit Farben besteht einfach aus einer zulässigen Färbung von und einer zulässigen Färbung von , es gibt darüber hinaus keine weitere Bedingung, da es ja keine Kanten zwischen und gibt. Die Anzahl der zulässigen Gesamtfärbungen ist daher das Produkt der Anzahlen der einzelnen zulässigen Färbungen.