  We show that any minimal Cayley graph of a (finitely generated) generalized
dihedral or nilpotent group has chromatic number at most 3, while 4 colors are
sometimes necessary for soluble groups. On the other hand we construct graphs
of unbounded chromatic number that admit a proper edge coloring such that each
cycle has some color at least twice. The latter disproves a conjecture of
Babai'78 that would have implied that all minimal Cayley graphs have bounded
chromatic number -- a problem that remains open.
