Babai's independence-ratio conjecture for minimal Cayley graphs

From papers

Let G=(V,E)G=(V,E)) be a minimal Cayley graph, and let α(G)\alpha(G) denote the size of its largest independent set.

Babai's conjecture. For every ε>0\varepsilon>0, there exists a minimal Cayley graph G=(V,E)G=(V,E) such that

α(G)εV.\alpha(G) \leq \varepsilon|V|.

This conjecture, mentioned by Babai in connection with the chromatic number of minimal Cayley graphs, would imply minimal Cayley graphs with arbitrarily large chromatic number. Its resolution status is not specified in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ignacio García-Marco and Kolja Knauer, “Coloring minimal Cayley graphs”, arXiv:2405.19543 (2024).

Solutions 0

No solutions have been posted yet.