Theorems and computations in circular colourings of graphs
M. Ghebleh · Summit (Simon Fraser University) · 2007
The circular chromatic number provides a more refined measure of colourability of graphs, than does the ordinary chromatic number. Thus circular colouring is of substantial importance wherever graph colouring is studied or applied, for example, to scheduling problems of periodic nature. Precisely, the circular chromatic number of a graph G is the smallest ratio p/q of positive integers p and q for which there exists a mapping c:V(G)->{1,2,...,p} such that q<=|c(u)-c(v)|<=p-q for every edge uv of G. We present some known and new results regarding the computation of the circular chromatic number. In particular, we prove a lemma which can be used to improve the ratio of some circular colourings. These results are later used to bound the circular chromatic number of the plane unit-distance graph, the projective plane orthogonality graph, generalized Petersen graphs, and squares of graphs. Some of the computations in this thesis are computer assisted. Nesetril's "pentagon problem", asks whether the circular chromatic number of every cubic graph having sufficiently high girth is at most 5/2. We prove that the statement of the pentagon colouring problem is false with odd-girth in place of girth; and that if the pentagon colouring problem is true then the girth requirement is at least 10. Additionally, we present results of extensive computations of the circular chromatic numbers of small cubic graphs with girth at most 10. We also prove that every subcubic graph with girth at least 9 which can be embedded in either the plane, the projec tive plane, the torus, or the Klein bottle, has circular chromatic number strictly less than 3. Finally we investigate circular edge colourings of cubic graphs. In particular, we establish the circular chromatic index for several infinite families of snarks, namely Isaacs' flower snarks, Goldberg snarks, and generalized Blanusa snarks.