Chromatic polynomial

The chromatic polynomial is a graph of the number of possible node coloring with colors, ie the number of coloring all nodes in the graph, so that nodes that are connected by an edge, carry different colors.

Examples

The chromatic polynomial is a complete graph

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

Properties

For each graph, there is a number such that for all. This number is the chromatic number of the graph and indicates how many colors are needed for a valid node coloring at least.

First, it is not clear at all that is a polynomial in, but this can be inductively show that applies for all edges: (where one graph is caused by contraction of edge e).