chromatic polynomial

Let $G$ be a graph (in the sense of graph theory) whose set $V$ of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural number $x$, let $\chi (G,x)$, or just $\chi (x)$, denote the number of $x$-colorations of $G$, i.e. the number of mappings $f:V\to \{1,2,\mathrm{\dots },x\}$ such that $f(a)\ne f(b)$ for any pair $(a,b)$ of adjacent vertices. Let us prove that $\chi$ (which is called the chromatic polynomial of the graph $G$) is a polynomial function in $x$ with coefficients in $\mathbb{Z}$. Write $E$ for the set of edges in $G$. If $|E|$=0, then trivially $\chi (x)=x^{|V|}$ (where $|\cdot |$ 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

$$\chi (G,x)=\chi (K,x)-\chi (H,x)$$ (1)

for all $x\in \mathbb{N}$, because the polynomial $\chi (K,x)$ is the number of colorations of the vertices of $G$ which might or might not be valid for the edge $e$, while $\chi (H,x)$ is the number which are not valid. By induction on $|E|$, (1) shows that $\chi (G,x)$ is a polynomial over $\mathbb{Z}$.

By refining the argument a little, one can show

$$\chi (x)=x^{|V|}-|E|x^{|V|-1}+\mathrm{\dots }\pm s{x}^k,$$

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-Rota inversion formula (see Moebius Inversion), or directly by induction, one can prove

$$\chi (x)=\sum _{F\subset 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 that $F$ 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 $\chi (G,x)>0$ or, equivalently, such that $\chi (G,x)\ne 0$.

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

$$t(x,y)=\sum _{F\subset 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.

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