Chromatic polynomial

from Wikipedia, the free encyclopedia

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.


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 .

The chromatic polynomial of a complete graph is

The color of the first node can always be chosen freely and there are still colors left for the coloring of the -th node .


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.

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


Web links