Chromatisches Polynom/Konstruktionen/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

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