Colouring Cayley Graphs

Mathematics;Cayley graphs;codes;projective geometry

Chu, Lei

University of Waterloo

关键词: Mathematics;    Cayley graphs;    codes;    projective geometry;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1125/1/l4chu2005.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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 n vertices with valency greater than n/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ⁿ vertices and valency greater than 2ⁿ/4 are either bipartite or 4-colourable.