García Marco, IgnacioKnauer, Kolja2025-12-032025-12-032025-01-100195-6698https://hdl.handle.net/2445/224639In 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.9 p.application/pdfengcc-by-nc (c) García Marco, Ignacio et al., 2025http://creativecommons.org/licenses/by-nc/4.0/Teoria de grafsGeometria combinatòriaGraph theoryCombinatorial geometryinfo:eu-repo/semantics/article7560652025-12-03info:eu-repo/semantics/openAccess