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.

Fitxers

884399.pdf (415.53 KB)

Tipus de document

Article

Versió

Versió publicada

Data de publicació

2025-01-10

Llicència de publicació

cc-by-nc (c) García Marco, Ignacio et al., 2025
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

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

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

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

Teoria de grafs, Geometria combinatòria

Matèries (anglès)

Graph theory, Combinatorial geometry

Citació

Col·leccions

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

Citació

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

Exportar metadades

JSON - METS

Compartir registre