# metadata.dc.description.abstract[].value
In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper 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 address a related question proposed by Babai in 1978 by constructing graphs of unbounded chromatic number that admit a proper edge coloring such that each cycle has some color at least twice. The latter can be viewed as a step towards confirming Babai’s 1994 conjecture – a problem that remains open.

# metadata.dc.rights[].value
cc-by-nc (c) García Marco, Ignacio et al., 2025

# metadata.dc.source[].value
Articles publicats en revistes (Matemàtiques i Informàtica)