Amb motiu del tancament d'estiu, la validació de documents es reprendrà a partir del 28 d'agost de 2026. Disculpeu les molèsties.
Con motivo del cierre de verano, la validación de documentos se reanudará a partir del 28 de agosto de 2026. Disculpad las molestias
Due to the summer closure, document validation will resume starting August 28, 2026. We apologize for any inconvenience.

Files

884399.pdf (415.53 KB)

Document type

Article

Version

Published version

Publication date

2025-01-10

Publication license

cc-by-nc (c) García Marco, Ignacio et al., 2025
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/224639

Coloring minimal Cayley graphs.

Journal Title

Authors

Director/Tutor

Journal ISSN

Volume Title

Related resource

https://doi.org/10.1016/j.ejc.2024.104108

Abstract

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.

Subject

Teoria de grafs, Geometria combinatòria

Subject (English)

Graph theory, Combinatorial geometry

Citation

Collections

Articles publicats en revistes (Matemàtiques i Informàtica)

Citation

GARCÍA MARCO, Ignacio and KNAUER, Kolja. Coloring minimal Cayley graphs. European Journal of Combinatorics. 2025. ISSN 0195-6698. [consulted: 8 of August of 2026]. Available at: https://hdl.handle.net/2445/224639

Export metadata

JSON - METS

Share record