chromatic polynomial (original) (raw)
Let G be a graph (in the sense of graph theory
) whose set Vof vertices is finite and nonempty, and which has no loops ormultiple edges. For any natural number
x, let χ(G,x), or just χ(x), denote the number of x-colorations of G, i.e. the number ofmappings 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 set
). 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 induction on |E|, (1) shows that χ(G,x) is a polynomial over ℤ.
By refining the argument 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 components of G, and the coefficients alternate in sign.
With the help of the Möbius-Rotainversion formula (see Moebius Inversion), or directly by induction, one can prove
| χ(x)=∑F⊂E(-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 thatF is equal to the span of F; all other summands cancel out in pairs.)
The chromatic number
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 matroid (E,r), is this function of two variables:
| t(x,y)=∑F⊂E(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.