Colouring Cayley Graphs
Abstract
We will discuss three ways to bound the chromatic number on a Cayley graph.
1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three.
2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on <i>n</i> vertices with valency greater than <i>n</i>/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs.
3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2<sup>n</sup> vertices and valency greater than 2<sup>n</sup>/4 are either bipartite or 4-colourable.
Collections
Cite this version of the work
Lei Chu
(2005).
Colouring Cayley Graphs. UWSpace.
http://hdl.handle.net/10012/1125
Other formats