# 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}$