Return to search

Colouring Cayley Graphs

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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1125
Date January 2005
CreatorsChu, Lei
PublisherUniversity of Waterloo
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
RightsCopyright: 2005, Chu, Lei. All rights reserved.

Page generated in 0.0016 seconds