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 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.

[发布机构] University of Waterloo

[效力级别] Cayley graphs

[关键词] Mathematics;Cayley graphs;codes;projective geometry