Carregant...
Fitxers
Tipus de document
ArticleVersió
Versió publicadaData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/224639
Coloring minimal Cayley graphs.
Títol de la revista
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
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.
Matèries
Matèries (anglès)
Citació
Citació
GARCÍA MARCO, Ignacio, KNAUER, Kolja. Coloring minimal Cayley graphs.. _European Journal of Combinatorics_. 2025. [consulta: 25 de gener de 2026]. ISSN: 0195-6698. [Disponible a: https://hdl.handle.net/2445/224639]