Babai's independence-ratio conjecture for minimal Cayley graphs
Babai's independence-ratio conjecture for minimal Cayley graphs
Let ) be a minimal Cayley graph, and let denote the size of its largest independent set.
Babai's conjecture. For every , there exists a minimal Cayley graph such that
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
Sign in to submit a solution.
No solutions have been posted yet.