chromatic polynomial
Let be a graph (in the sense of graph theory) whose set of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural number , let , or just , denote the number of -colorations of , i.e. the number of mappings such that for any pair of adjacent vertices. Let us prove that (which is called the chromatic polynomial of the graph ) is a polynomial function in with coefficients in . Write for the set of edges in . If =0, then trivially (where denotes the number of elements of a finite set). If not, then we choose an edge and construct two graphs having fewer edges than : is obtained from by contracting the edge , and is obtained from by omitting the edge . We have
(1) |
for all , because the polynomial is the number of colorations of the vertices of which might or might not be valid for the edge , while is the number which are not valid. By induction on , (1) shows that is a polynomial over .
By refining the argument a little, one can show
for some nonzero integer , where is the number of connected components of , and the coefficients alternate in sign.
With the help of the Möbius-Rota inversion formula (see Moebius Inversion), or directly by induction, one can prove
where the sum is over all subsets of , and denotes the rank of in , i.e. the number of elements of any maximal cycle-free subset of . (Alternatively, the sum may be taken only over subsets such that is equal to the span of ; all other summands cancel out in pairs.)
The chromatic number of is the smallest such that or, equivalently, such that .
The Tutte polynomial of a graph, or more generally of a matroid , is this function of two variables:
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 |