Chromatic polynomial

The chromatic polynomial indicates the number of possible node colors with colors for a graph , i.e. H. the number of times that all nodes of the graph are colored, so that nodes connected by an edge have different colors. ${\displaystyle \chi (G,\lambda )}$ ${\displaystyle G}$ ${\displaystyle \lambda }$

Examples

The chromatic polynomial of a graph with isolated nodes is . Each of the nodes can take on one of the colors independently of the others . ${\displaystyle n}$ ${\displaystyle \chi (G,\lambda )=\lambda ^{n}}$ ${\displaystyle n}$ ${\displaystyle \lambda }$

The chromatic polynomial of a complete graph is ${\displaystyle K_{n}}$

${\displaystyle \chi (K_{n},\lambda )=\prod _{i=0}^{n-1}(\lambda -i)=\lambda (\lambda -1)\cdots (\lambda -n+1)}$

The color of the first node can always be chosen freely and there are still colors left for the coloring of the -th node . ${\displaystyle (i+1)}$ ${\displaystyle \lambda -i}$

properties

For every graph there is a number , so for all . This number is the chromatic number of the graph and indicates how many colors are required for a permissible node coloring. ${\displaystyle \chi (G)}$ ${\displaystyle \chi (G,\lambda )=0}$ ${\displaystyle \lambda <\chi (G)}$

At first it is not clear that there is a polynomial in at all , but this can be shown inductively, since the following applies for all edges : (where is the graph that is created by the edge contraction of e). ${\displaystyle \chi }$ ${\displaystyle \lambda }$ ${\displaystyle e\in E}$ ${\displaystyle \chi (G,\lambda )=\chi (G\setminus \{e\},\lambda )-\chi (G/e,\lambda )}$ ${\displaystyle G/e}$

literature

• Martin Aigner : Combinatorial theory. Springer, 1979, ISBN 0-387-90376-3
• Swamy M., Thulasiraman K .: Graphs, Networks and Algorithms. Warrior Pub. Co., 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
• Graham R. (Ed.), Grötschel M. (Ed.), László L. (Ed.): Handbook of Combinatorics. Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3

Web links

Wikiversity: A lecture on the chromatic polynomial as part of a discrete mathematics  course - course materials

• Eric W. Weisstein : Chromatic Polynomial . In: MathWorld (English).