chromatic polynomial


Let G be a graph (in the sense of graph theoryMathworldPlanetmath) whose set V of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural numberMathworldPlanetmath x, let χ(G,x), or just χ(x), denote the number of x-colorations of G, i.e. the number of mappings f:V{1,2,,x} such that f(a)f(b) for any pair (a,b) of adjacent vertices. Let us prove that χ (which is called the chromatic polynomial of the graph G) is a polynomial function in x with coefficients in . Write E for the set of edges in G. If |E|=0, then trivially χ(x)=x|V| (where || denotes the number of elements of a finite setMathworldPlanetmath). If not, then we choose an edge e and construct two graphs having fewer edges than G: H is obtained from G by contracting the edge e, and K is obtained from G by omitting the edge e. We have

χ(G,x)=χ(K,x)-χ(H,x) (1)

for all x, because the polynomial χ(K,x) is the number of colorations of the vertices of G which might or might not be valid for the edge e, while χ(H,x) is the number which are not valid. By inductionMathworldPlanetmath on |E|, (1) shows that χ(G,x) is a polynomial over .

By refining the argumentPlanetmathPlanetmath a little, one can show

χ(x)=x|V|-|E|x|V|-1+±sxk,

for some nonzero integer s, where k is the number of connected componentsMathworldPlanetmath of G, and the coefficients alternate in sign.

With the help of the Möbius-Rota inversion formulaMathworldPlanetmathPlanetmath (see Moebius Inversion), or directly by induction, one can prove

χ(x)=FE(-1)|F|x|V|-r(F)

where the sum is over all subsets F of E, and r(F) denotes the rank of F in G, i.e. the number of elements of any maximal cycle-free subset of F. (Alternatively, the sum may be taken only over subsets F such that F is equal to the span of F; all other summands cancel out in pairs.)

The chromatic numberMathworldPlanetmath of G is the smallest x>0 such that χ(G,x)>0 or, equivalently, such that χ(G,x)0.

The Tutte polynomial of a graph, or more generally of a matroidMathworldPlanetmath (E,r), is this function of two variables:

t(x,y)=FE(x-1)r(E)-r(F)(y-1)|F|-r(F).

Compared to the chromatic polynomial, the Tutte contains more information about the matroid. Still, two or more nonisomorphic matroids may have the same Tutte polynomial.

Title chromatic polynomial
Canonical name ChromaticPolynomial
Date of creation 2013-03-22 13:58:25
Last modified on 2013-03-22 13:58:25
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 8
Author bbukh (348)
Entry type Definition
Classification msc 05C15
Classification msc 05B35
Related topic Matroid
Related topic ChromaticNumber
Defines Tutte polynomial