im Rahmen des Vier-Farben-Problems eingeführtes Polynom, das von großer Bedeutung innerhalb der Graphenthorie ist, denn ein chromatisches Polynom liefert bei gegebener natürlicher Zahl k die Anzahl der möglichen Eckenfärbungen eines Graphen mit k Farben.

Es sei G ein Graph mit der Eckenmenge E(G) und k eine natürliche Zahl. Die Anzahl der Abbildungen h : E(G) → {1, 2,…, k} mit h(x) ≠ h(y) für alle adjazenten Ecken x und y bezeichnen wir mit P(k, G). Damit bedeutet P(k, G) die Anzahl der verschiedenen k-Eckenfärbungen von G. Ein Graph G besitzt natürlich genau dann eine k-Eckenfärbung, wenn P(k, G) > 0 gilt.

Beim Versuch, das Vier-Farben-Problem zu lösen, wurde in den Jahren 1912 und 1913 die Größe P(k, L) von G.D. Birkhoff für LandkartenL eingeführt. Als eines seiner Hauptergebnisse hat Birkhoff gezeigt, daß P(k, L) stets ein Polynom in k ist, welches heute den Namen chromatisches Polynom trägt.

Einige von Birkhoffs Resultaten und weitere Ergänzungen durch H. Whitney (1932), R.C. Read (1968) und G.H.J. Meredith (1972) kann man für beliebige Graphen zu einem Satz zusammenfassen und diesen dann Fundamentalsatz über chromatische Polynome nennen.

Besteht ein Graph H aus q isolierten Ecken, so ergibt ein einfaches Abzählargument die Identität P(k, H) = k^q. Der Fundamentalsatz folgt induktiv aus dieser Identität und der einfach zu beweisenden, aber wichtigen Rekursionsformel für chromatische Polynome \begin{eqnarray}P(k,G)=P(k,G-l)-P(k,{G}^{(l)}),\end{eqnarray} wobei l eine beliebige Kante des Graphen G ist, und G^(l) der durch Kontraktion der Kante l entstandene Graph.

Ist G ein Graph der Ordnung n, so gilt für k ∈ ℕ \begin{eqnarray}P(k,G)=\displaystyle \sum _{i=0}^{n}{(-1)}^{i}{a}_{i}(G){k}^{n-i}.\end{eqnarray}

Ist m die Anzahl der Kanten und η die Anzahl der Zusammenhangskomponenten von G, so gelten für das chromatische Polynom P(k, G) folgende Aussagen:

1. Es sei l eine Kante von G. Setzt mana₋₁(G^(l)) = 0, so gilt für alle 0 ≤ i ≤ na_i(G) = a_i(G – l) + a_i–1(G^(l)).
2. P(k, G) ist ein Polynom vom Grad n mita₀(G) = 1, a₁(G) = m unda_n(G) = 0.
3. Die Koeffizienten a_i (G) sind nicht-negative ganze Zahlen, und es gilt a_i(G) ≠ 0 genau dann, wenn 0 ≤ i ≤ n – η ist.
4. Für alle 0 ≤ i ≤ n – η gilt\begin{eqnarray}(\begin{array}{c}n-\eta \\ i\end{array})\le {a}_{i}(G)\le (\begin{array}{c}m\\ i\end{array}).\end{eqnarray}
5. Bezeichnet man mit g(G) die Taillenweite vonG, so ist \({a}_{i}(G)=(m\\ i)\)für 0 ≤ i ≤ g(G) – 2.
6. SindG₁, G₂,…,G_η die Komponenten von G, so gilt\begin{eqnarray}P(k,G)=\displaystyle \prod _{i=1}^{\eta }P(k,{G}_{i}).\end{eqnarray}
7. Ist G die Vereinigung zweier Teilgraphen G₁und G₂, deren Durchschnitt ein vollständiger Graph K_r ist, so gilt\begin{eqnarray}P(k,G)=\frac{P(k,{G}_{1})P(k,{G}_{2})}{k(k-1)\ldots (k-r+1)}.\end{eqnarray}

Dieser Fundamentalsatz zeigt, daß sich an den Koeffizienten des chromatischen Polynoms einige Eigenschaften des Graphen ablesen lassen. Der Idealfall wäre, wenn man den Graphen aus dem chromatischen Polynom eindeutig zurückgewinnen könnte. Daß dies aber im allgemeinen nicht möglich ist, zeigt schon das nächste Ergebnis, das sich ohne allzu großen Aufwand aus dem Fundamentalsatz gewinnen läßt.

Ein Graph H ist genau dann ein Wald der Ordnung n mit η Komponenten, wenn\begin{eqnarray}P(k,H)={k}^{\eta }{(k-1)}^{n-\eta }\end{eqnarray}gilt. Insbesondere besitzt damit jeder Baum T der Ordnung n das gleiche chromatische Polynom\begin{eqnarray}P(k,T)=k{(k-1)}^{n-1}.\end{eqnarray}

Zur algorithmischen Bestimmung eines chromatischen Polynoms kann man die Rekursionsformel solange anwenden, bis alle auftretenden Graphen Wälder sind oder bis nur noch vollständige Graphen vorliegen. Dabei ist die erste Methode günstig für Graphen mit wenig Kanten und die zweite für Graphen mit vielen Kanten. Die kleinste natürliche Zahl k mit P(k, G) > 0 ist natürlich die chromatische Zahl χ(G). Daraus ergibt sich zusammen mit der Rekursionsformel \begin{eqnarray}\chi (G-l)=\min \{\chi ({G}^{(l)}),\chi (G)\}.\end{eqnarray}

Wegen dieser Gleichung führt folgende Methode zu einer Eckenfärbung von G. Man wende die Rekursionsformel solange an, bis alle auftretenden Graphen vollständig sind. Versieht man den kleinsten vollständigen Graphen mit einer Eckenfärbung, so erhält man rückwärts eine Eckenfärbung des Ausgangsgraphen.

Allerdings ist dieses Verfahren nicht effizient, denn ist r die Anzahl der zum vollständigen Graphen fehlenden Kanten, so benötigt man 2^r Schritte. Naturgemäß ist bis heute kein polynomialer Algorithmus zur Bestimmung des chromatischen Polynoms bekannt, denn auch dieses Problem ist NP-vollständig.

Die folgende interessante Interpretation für die Koeffizienten des chromatischen Polynoms eines Graphen G mit n Ecken und m Kanten geht auf H. Whitney (1932) zurück:

Es gilt\begin{eqnarray}{(-1)}^{i}{a}_{i}(G)=\displaystyle \sum _{t=0}^{m}{(-1)}^{t}N(t,n-i),\end{eqnarray}wobei N(t, j) diejenigen Faktoren von G mit t Kanten und j Komponenten zählt.

Mit dieser Formel lassen sich weitere Koeffizienten des chromatischen Polynoms berechnen.