11 ***Chromatic number and polynomials***11.2 Chromatic Polynomials 11.4 Edge-Chromatic number

11.3 Some bounds on chromatic number.

We shall now derive some more bounds for chromatic number. See [Sudakov 2019, Chapters 7 and 8] for more results on graph colouring and also some interesting applications. We give some simple bounds here. Some will be proved and some are left as exercises.

Lemma 11.8.

1.

$\chi(G)\geq\frac{|V(G)|}{\alpha(G)}$ where recall that $\alpha(G)$ is the independence number.
2.

For any $U\subset V$ , $\chi(G)\leq\chi(G[U])+\chi(G[V\setminus U])$ ( $\leq 2\chi(G)$ ) where $G[U]$ is the induced subgraph on $U$ .
3.

If $G=G_{1}\cup G_{2}$ with $V(G_{i})=V(G),i=1,2$ then $\chi(G)\leq\chi(G_{1})\chi(G_{2})$ .
4.

$\chi(G)\chi(\bar{G})\geq|V|$ .

Proof.

(1)

Let $f$ be a $k$ -colouring where $k=\chi(G)$ . Hence, $V(G)=f^{-1}(1)\cup f^{-1}(2)\cdots\cup f^{-1}(k)$ . If $v_{i},v_{j}\in f^{-1}(m)$ for some $m$ then $v_{i}\nsim v_{j}$ . Hence, $f^{-1}(m)$ are independent sets. $|f^{-1}(m)|\leq\alpha(G)$ . Also, $f^{-1}(m)\cap f^{-1}(n)=\emptyset,\,\forall m\neq n$ .

$\therefore|V(G)|=\sum_{i=1}^{k}|f^{-1}(i)|\leq k\alpha(G)$
(2)

We can colour $U$ using $\chi(G[U])$ colours and now choose another $\chi(G[V\setminus U])$ colours to colour $V\setminus U$ . Thus $G$ has been coloured using $\chi(G[U])+\chi(G[V\setminus U])$ colours.
(3)

If $c_{i}$ are colourings of $G_{i}$ , define $c=(c_{1},c_{2})$ . Note that if $u\sim v$ then $(u,v)\in G_{i}$ for some $i$ and for that $i$ , $c_{i}(u)\neq c_{i}(v)$ . Thus $c(u)\neq c(v)$ and so $c$ is a colouring of $G$ .
(4)

Follows from (3) as $G\cup\bar{G}=K_{|V|}$ , complete graph on $V$ .

∎

Our argument to show that $\chi\leq\Delta+1$ can be refined to give a greedy way to colour a graph and yielding an improved bound as follows. Call a graph $k$ -degenerate if every subgraph has a vertex of degree at most $k$ .

Exercise(A) 11.9.

Show that $G$ is $k$ -degenerate iff there is an ordering of vertices $v_{1},\ldots,v_{n}$ such that each $v_{i}$ has at most $k$ neighbours among $v_{1},\ldots,v_{i-1}$ .

Exercise(A) 11.10.

Show that a $k$ -degenerate graph is $(k+1)$ -colourable. In particular, if $d(G)$ is the minimum $k$ such that $G$ is $k$ -degenerate then $\chi(G)\leq d(G)+1$ .

Exercise 11.11.

Show that $d(G)\leq\Delta(G)$ and find examples where $d(G)$ is small and $\Delta(G)$ is large