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 |