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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1125 |
| Date | January 2005 |
| Creators | Chu, Lei |
| Publisher | University of Waterloo |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Rights | Copyright: 2005, Chu, Lei. All rights reserved. |
Page generated in 0.0018 seconds