  Vertex colouring is a well-known problem in combinatorial optimisation, whose
alternative integer programming formulations have recently attracted
considerable attention. This paper briefly surveys seven known formulations of
vertex colouring and introduces a formulation of vertex colouring using a
suitable clique partition of the graph. This formulation is applicable in
timetabling applications, where such a clique partition of the conflict graph
is given implicitly. In contrast with some alternatives, the presented
formulation can also be easily extended to accommodate complex performance
indicators (``soft constraints'') imposed in a number of real-life course
timetabling applications. Its performance depends on the quality of the clique
partition, but encouraging empirical results for the Udine Course Timetabling
problem are reported.
