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 ormultiple 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 ofmappings $f:V\to \{1,2,\mathrm{\dots },x\}$ such that $f(a)\ne f(b)$ for anypair $(a,b)$ of adjacent vertices.Let us prove that $\chi$ (which is called thechromatic 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 elementsof a finite set).If not, then we choose an edge $e$ and construct two graphshaving fewer edges than $G$: $H$ is obtained from $G$ by contractingthe 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 numberof colorations of the vertices of $G$ which might or might not bevalid for the edge $e$, while $\chi (H,x)$ is the number whichare not valid.By induction on $|E|$, (1) shows that $\chi (G,x)$ isa 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 numberof 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

$$\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 therank of $F$ in $G$, i.e. the number of elements ofany 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 cancelout 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 informationabout the matroid.Still, two or more nonisomorphic matroids may have the same Tutte polynomial.