Graph Colouring

Given a graph $G$, a valid colouring of $G$ is defined as an assignment of colours to the vertices of $G$ such that no two adjacent vertices share the same colour. If it is possible to produce a valid colouring of $G$ using at most $k$ different colours, then we say that $G$ is $k$-colourable. It is well-known and easy to see that every graph with maximum degree $d$ is $(d+1)$-colourable. The complete graph and the odd cycle are two trivial examples of graphs that are $(d+1)$-colourable but not $d$-colourable.

In 1941, Leonard Brooks proved that these are, in fact, the only two cases where $d+1$ colours are necessary. In other words, if $G$ is not an odd cycle and does not contain $K_{d+1}$ (the complete graph on $d+1$ vertices) as a subgraph, then $d$ colours are sufficient to produce a valid colouring of $G$. In 1973, Lovasz came up with a nice one page proof of Brooks' theorem. We will discuss this proof in the talk. Time permitting, we will also see whether a triangle free graph is $c$-colourable, for some constant $c$.