Colouring Preliminaries

We will be discussing colouring the vertices and edges of graphs. A graph G is a set V = V (G) of vertices and a set E = E(G) of edges,each linking a pair of vertices, its endpoints (formally, an edge is an unordered pair of vertices and thus our graphs have no loops or multiple edges), which are adjacent. We assume the reader has a basic knowledge of graph theory. A k-colouring of the vertices of a graph G is an assignment of k colours (often the integers 1,..., k) to the vertices of G so that no two adjacent vertices get the same colour. The chromatic number of G, denoted χ(G), is the minimum k for which there is a k-colouring of the vertices of G. The set S _j of vertices receiving colour j is a colour class and induces a graph with no edges, i.e. it is a stable set or independent set. So, a k-colouring of the vertices of G is simply a partition of V(G) into k stable sets and the chromatic number of G is the minimum number of stable sets into which the vertices of G can be partitioned.