imported>RonMeier: /* Literatur */ Formatierung

2025-12-02T18:39:54Z

Literatur: Formatierung

Neue Seite

Das '''chromatische [[Polynom]]''' <math>\chi(G, \lambda)</math> gibt zu einem [[Graph (Graphentheorie)|Graphen]] <math>G</math> die Anzahl der möglichen [[Färbung (Graphentheorie)|Knotenfärbungen]] mit <math>\lambda</math> Farben an, d. h. die Anzahl der Färbungen aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.

== Beispiele ==

Das chromatische Polynom eines Graphen mit <math>n</math> isolierten Knoten ist <math>\chi(G, \lambda)=\lambda^n</math>. Jeder der <math>n</math> Knoten kann unabhängig von den anderen eine der <math>\lambda</math> Farben annehmen.

Das chromatische Polynom eines [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math> ist
:<math>\chi(K_n, \lambda) = \prod_{i=0}^{n-1} (\lambda-i) = \lambda(\lambda-1)\cdots(\lambda-n+1)</math>
Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des <math>(i+1)</math>-ten Knotens sind dann noch <math>\lambda-i</math> Farben übrig.

== Eigenschaften ==

Für jeden Graphen gibt es eine Zahl <math>\chi(G)</math>, sodass <math>\chi(G, \lambda) = 0</math> für alle <math>\lambda < \chi(G)</math>. Diese Zahl ist die [[chromatische Zahl]] des Graphen und gibt an, wie viele Farben für eine zulässige Knotenfärbung mindestens benötigt werden.

Es ist zunächst einmal nicht klar, dass <math>\chi</math> überhaupt ein Polynom in <math>\lambda</math> ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten <math>e\in E</math> gilt: <math>\chi(G, \lambda)=\chi(G\setminus\{e\}, \lambda) - \chi(G/e, \lambda)</math> (wobei <math>G/e</math> derjenige Graph ist, der durch [[Kantenkontraktion]] von e entsteht).

== Literatur ==

* [[Martin Aigner]]: ''Combinatorial theory.'' Springer, 1979, ISBN 0-387-90376-3.
* M. Swamy, K. Thulasiraman: ''Graphs, Networks and Algorithms.'' Krieger Pub., 1980, ISBN 0-471-03503-3.
* [[William Thomas Tutte]]: ''Graph Theory.'' Addison-Wesley, 1984, ISBN 0-201-13520-5.
* [[Herbert Wilf]]: ''Algorithms and Complexity.'' Prentice-Hall, 1986, ISBN 0-13-022054-X.
* R. Graham, [[Martin Grötschel|M. Grötschel]] , L. László (Hrsg.): ''Handbook of Combinatorics.'' Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3.


== Weblinks ==

{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 24|Eine Vorlesung über das chromatische Polynom im Rahmen eines Kurses zur diskreten Mathematik}}
* {{MathWorld|ChromaticPolynomial|Chromatic Polynomial}}

[[Kategorie:Graphentheorie]]
[[Kategorie:Polynom]]

Chromatisches Polynom - Versionsgeschichte

imported>RonMeier: /* Literatur */ Formatierung