Uniquely colorable Cayley graphs

Walter Klotz, Torsten Sander


It is shown that the chromatic number χ(G) = k of a uniquely colorable Cayley graph G over a group Γ  is a divisor of ∣Γ ∣ = n. Each color class in a k-coloring of G is a coset of a subgroup of order n / k of Γ . Moreover, it is proved that (k − 1)n is a sharp lower bound for the number of edges of a uniquely k-colorable, noncomplete Cayley graph over an abelian group of order n. Finally, we present constructions of uniquely colorable Cayley graphs by graph products.


Vertex coloring, color classes, Cayley graph

Full Text:


DOI: https://doi.org/10.26493/1855-3974.879.d47

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications