An upper bound for the chromatic number of a graph and its application to timetabling problems

Abstract

This paper points out the connection between the basic scheduling or timetabling problem with the well known problem of colouring the vertices of a graph in such a way that (i) no two adjacent vertices are the same colour and (ii) the number of colours used is a minimum. We give an algorithm for colouring a graph subject to (i) and give a new easily determined bound for the number of colours needed. This same bound is also a new upper bound for the chromatic number of a graph in terms of the degrees of its vertices.