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
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.
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.
|Date of creation||2013-03-22 13:58:25|
|Last modified on||2013-03-22 13:58:25|
|Last modified by||bbukh (348)|