11.1 Graph coloring

One can compute chromatic number easily for simple graphs; See Section 11.7. Trivially, we have that $cl(G)\le \chi (G)\le \mathrm{\Delta }(G)+1$ where $cl(G)$ is the size of the largest clique (complete subgraph) in $G$. The lower bound is trivial as each of the vertices in the clique needs to be assigned a different colour. As for the upper bound, start with the vertex of degree $\mathrm{\Delta }(G)$ say $1$. Assign $1$ and all its neighbours $\mathrm{\Delta }(G)+1$ distinct colours. Pick an uncoloured vertex. Note that since it has at most $\mathrm{\Delta }(G)$ coloured neighbours, we can assign it a new colour among $\mathrm{\Delta }(G)+1$ distinct colours.

Further, a graph is $k$-colourable iff we can partition into $k$ independent sets.

For some motivation on chormatice number in scheduling or allocation problems, see [Sudakov 2019, Section 7.2].