Babai's independence-ratio conjecture for minimal Cayley graphs

About 2 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.