Hall 123

Basics of Graph Coloring

Mathew Francis

ISI Chennai

A vertex-colouring of a graph is an assignment of colours to the vertices of a graph in such a way that no two adjacent vertices get the same colour. The chromatic number of a graph is the minimum number of colours required in any vertex-colouring of the graph. Similarly, an edge-colouring of a graph is an assignment of colours to the edges of a graph such that no two edges incident on the same vertex get the same colour. The chromatic index of the graph is the minimum number of colours required in any edge-colouring of the graph. We take a look at some basic theorems about vertex-colouring and edge-colouring of graphs.