Chromatic numbers of Cayley graphs from minimal involution generators

Are chromatic numbers of finite-group Cayley graphs bounded when the generating set is minimal and consists of involutions? The target is a family with chromatic number at least k for every k.

Why it matters and what counts as progress

Why it matters: It tests whether minimality and involution structure force any universal colouring bound.

What counts as progress: Construct minimally generated involution Cayley graphs of arbitrarily large chromatic number, or prove a bound under an additional group restriction.

How the problem developed

1978 · Question [1]
László Babai Asked whether minimal Cayley graphs have chromatic number bounded by a universal constant.
1994 · Conjecture [1]
László Babai Conjectured that finite minimal Cayley graphs can have unbounded chromatic number.
2024 · Partial result [1]
Ignacio García-Marco and Kolja Knauer Proved chromatic number at most three for minimal Cayley graphs of generalized dihedral or nilpotent groups, while leaving Babai’s general question open.
6 Aug 2026 · AI-assisted result [2]
James Davies, Meike Hatzel and Liana Yepremyan Reported finite groups with minimal involution generating sets whose Cayley graphs have arbitrarily large chromatic number.