11 ***Chromatic number and polynomials***11.1 Graph coloring 11.3 Some bounds on chromatic number.

11.2 Chromatic Polynomials

Let $G$ be a graph on $n$ vertices. Let $P(G,q),q\in\mathbb{N}_{*}$ be the number of ways of colouring (properly) a graph with $q$ colours. More formally,

P(G,q)=|\{c:V\to[q]:c(u)\neq c(v)\forall u\sim v\}|.

We shall define $P(G,x),x\in\mathbb{R}$ to be the polynomial (if it exists) such that $P(G,q)$ is the number of proper $q$ -colourings of $G$ for $q\in\mathbb{N}_{*}$ . $P(G,x)$ is called the chromatic polynomial of $G$ . Observe that if $g$ is a polynomial such that $g(q)=P(G,q)$ for all $q\in\mathbb{N}$ then $g\equiv P(G,.)$ and hence $P(G,x)$ is unique if it exists. We will now show that this is a monic polynomial of degree $n$ and other interesting properties.

Let $G-e$ denote the graph with the edge $e$ removed. Let $G/e$ denote the graph with $e$ contracted i.e., if $e=(v,w)$ then we replace the vertices $v, w$ with $v^{\prime}$ and edges $v\sim x,w\sim y$ with $v^{\prime}\sim x,v^{\prime}\sim y$ . Observe that $G/e$ can be a multigraph. But this will not matter to us as proper colourings of a multigraph and its corresponding simple graph are the same.

Proposition 11.3.

(Delection-contraction principle ) For any edge $e=(v,w)\in G$ ,

P(G,q):=P(G-e,q)-P(G/e,q),q\in\mathbb{N}.

Proof.

The proof follows by two simple observations that any proper $q$ -colouring of $G$ is a proper $q$ -colouring of $G-e$ in which $v$ and $w$ receive distinct colours and any proper $q$ -colouring of $G-e$ in which $v$ and $w$ receive same colours is a proper $q$ -colouring of $G/e$ . ∎

If $E=\emptyset$ , trivially $P(G,q)=q^{n}$ and so $P(G,x)=x^{n}$ . Thus the chromatic polynomial exists and is monic in this case. Now using Proposition 11.3, we can inductively show that $P(G,x)$ is a polynomial in $q$ . Here are some very important properties. All the proofs will follow from deletion-contraction principle and induction. Our general proof strategy is as follows.

•

Assume $P(G,x)$ is a polynomial with some properties for $E=\emptyset$ .
•

Using uniqueness of chromatic polynomial and DCI, conclude that $P(G,x):=P(G-e,x)-P(G/e,x)$ is the chromatic polynomial of $G$ .
•

Using induction hypothesis and DCI, show that $P(G,x)$ satisfies appropriate property.

For abbreviation, we call this DCI argument in this section.

Lemma 11.4.

1.

$P(G,x)$ is a monic polynomial of degree $n$ .
2.

$\chi(G)=\min\{k\in\mathbb{N}:P(G,k)>0\}$ .

Now, let us assume that $P(G,x)=\sum_{i=1}^{n}a_{i}x^{i}$ (as $a_{0}=0$ trivially). Then we have that

3.

$\sum_{i=1}^{n}a_{i}=0$ or $P(G,x)=x^{n}$ .
4.

$a_{n-i}=(-1)^{i}|a_{n-i}|$ .
5.

$a_{n-1}=-|E|$ .

Proof.

1.

This claim holds for $E=\emptyset$ . Assume that it holds for $|E|<m$ and $|V|<n$ . Let $G$ be a graph with $|E|=m,|V|=n$ . By DC principle $P(G,q)=P(G-e,q)-P(G/e,q)$ for all $q\in\mathbb{N}$ and so $P(G,x):=P(G-e,x)-P(G/e,x)$ is the chromatic polynomial of $G$ . By induction hypothesis, $P(G-e,x)$ is a monic polynomial of degree $n$ and $P(G/e,x)$ is a monic polynomial of degree $n-1$ . So $P(G,x)$ is a monic polynomial of degree $n$ .
2.

This follows trivially by the two definitions.
3.

As for (4), observe that $\sum_{i=1}^{n}a_{i}=P(G,1)=$ no. of proper $1$ -colouring of $G$ .If $|E|\neq\emptyset$ , there exists no proper $1$ -colouring of $G$ and so $P(G,1)=0$ . Else $P(G,x)=x^{n}$ as required.
4.

We will apply the DCI argument again and prove (4),(5) and (6) together. The three identities can be verified for $E=\emptyset$ or $G$ has $1$ or $2$ vertices easily. Let

$P(G-e,x)=\sum_{i=0}^{n}(-1)^{i}|b_{n-i}|x^{n-i},\,\,P(G/e,x)=\sum_{i=0}^{n-1}(% -1)^{i}|c_{n-1-i}|x^{n-1-i}=\sum_{i=1}^{n}(-1)^{i-1}|c_{n-i}|x^{n-i}.$

Then by DC principle we have that

$P(G,x)=|b_{n}|x^{n}+\sum_{i=1}^{n}(-1)^{i}[|b_{n-i}|+|c_{n-i}|]x^{n-i}.$

(5) follows easily as $a_{n-i}=(-1)^{i}[|b_{n-i}|+|c_{n-i}|]$ .
5.

As for (6), observe by monicity of the chromatic polynomial, induction and DC principle that that

$|E(G)|=|E(G-e)|+1=-b_{n-1}+c_{n-1}=|b_{n-1}|+|c_{n-1}|=-a_{n-1},$

where in the second equality we have used (6) for $b_{n-1}$ .

∎

Lemma 11.5.

If $G$ has $k$ -components $G_{1},\ldots,G_{k}$ then

P(G,x)=\prod_{i=1}^{k}P(G_{i},x)

and further $a_{0}=\ldots=a_{k-1}=0$ .

Proof.

First equality follows trivially because any combination of $q$ -colourings of each component gives a $q$ -colouring of the full graph $G$ i.e.,

P(G,q)=\prod_{i=1}^{k}P(G_{i},q),q\in\mathbb{N}_{*}.

Since $deg(P(G_{i},x))\geq 1$ , we have that $a_{0}=\ldots=a_{k-1}=0$ ∎

Theorem 11.6.

$P(G,x)=\sum_{X\subset E}(-1)^{|X|}x^{\beta_{0}(X)}$ where $\beta_{0}(X)=\beta_{0}((V,X))$ .

Proof.

Enough to show that $P(G,q)=\sum_{X\subset E}(-1)^{|X|}q^{\beta_{0}(X)}$ for $q\in\mathbb{N}_{*}$ . Let $c:V\to[q]$ be an improper colouring if $c(u)=c(v)$ for some $u\sim v$ . Let $I C$ be the set of all improper colourings. For $e=(u,v)$ define $B_{e}:=\{c\in IC:c(u)=c(v)\}$ . Then we have that

	$\displaystyle P(G,q)$	$\displaystyle=q^{n}-\|IC\|=q^{n}-\|\cup_{e\in E}B_{e}\|$
		$\displaystyle=q^{n}-\sum_{\emptyset\supsetneq X\subset E}(-1)^{\|X\|-1}\|\cap_{e% \in X}B_{e}\|$
		$\displaystyle=q^{n}+\sum_{\emptyset\supsetneq X\subset E}(-1)^{\|X\|}\|\cap_{e\in X% }B_{e}\|.$

To complete the proof, enough to prove that for $\emptyset\supsetneq X\subset E$ , $|\cap_{e\in X}B_{e}|=q^{\beta_{0}(X)}$ . Suppose $X=\{e_{1},\ldots,e_{k}\}$ where $e_{i}=(u_{i},v_{i}),1\leq i\leq k$ . Let $C_{1},\ldots,C_{m}$ be the components in $(V,X)$ i.e., $m=\beta_{0}(X)$ . It is possible that $u_{i}=u_{j}$ or $v_{j}$ . Thus, we have that

	$\displaystyle\cap_{e\in X}B_{e}$	$\displaystyle=\{c:V\to[q]:c(u_{i})=c(v_{i}),1\leq i\leq k\}$
		$\displaystyle=\{c:V\to[q]:\mbox{$c$ is a constant on each $C_{i},1\leq i\leq m% $}\}$

The latter is obtained by choosing one colour for each component $C_{1},\ldots,C_{m}$ and so its cardinality if $q^{m}$ as required. ∎

Exercise(A) 11.7.

1.

Find the chromatic polynomial of complete graph $K_{n}$ , cycle $C_{n}$ , wheel graph $W_{n}$ (i.e., the graph obtained by adding a new vertex to $C_{n}$ and connecting it to all the $n$ vertices of $C_{n}$ ), path graph $P_{n}$ and the Petersen graph.
2.

Show that the coefficient of $x^{n-2}$ in the chromatic polynomial of a $n$ vertex graph is $\frac{m(m-1)}{2}-T$ where $T$ is the number of triangles and $m$ is the number of edges.
3.

Show that a graph with $n$ vertices is a tree iff $P(G,x)=x(x-1)^{n-1}$ .

	$\displaystyle P(G,q)$	$\displaystyle=q^{n}-\|IC\|=q^{n}-\|\cup_{e\in E}B_{e}\|$
		$\displaystyle=q^{n}-\sum_{\emptyset\supsetneq X\subset E}(-1)^{\|X\|-1}\|\cap_{e% \in X}B_{e}\|$
		$\displaystyle=q^{n}+\sum_{\emptyset\supsetneq X\subset E}(-1)^{\|X\|}\|\cap_{e\in X% }B_{e}\|.$