Uniquely colorable Cayley graphs

Walter Klotz, Torsten Sander

Abstract


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.


Keywords


Vertex coloring, color classes, Cayley graph

Full Text:

PDF ABSTRACTS (EN/SI)


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