  In this note, we present results for the colouring problem on small world
graphs created by rewiring square, triangular, and two kinds of cubic (with
coordination numbers 5 and 6) lattices. As the rewiring parameter p tends to 1,
we find the expected crossover to the behaviour of random graphs with
corresponding connectivity. However, for the cubic lattices there is a region
near p=0 for which the graphs are colourable. This could in principle be used
as an additional heuristic for solving real world colouring or scheduling
problems. Small worlds with connectivity 5 and p ~ 0.1 provide an interesting
ensemble of graphs whose colourability is hard to determine. For square
lattices, we get good data collapse plotting the fraction of colourable graphs
against the rescaled parameter parameter $p N^{-\nu}$ with $\nu = 1.35$. No
such collapse can be obtained for the data from lattices with coordination
number 5 or 6.
