Palette-sparsification conjecture at the local degree threshold
Palette-sparsification conjecture at the local degree threshold
Let be a graph on vertex set with degree at each vertex . Let be an arbitrary color set, let satisfy for every , and let each be a uniformly random -subset of , where
for fixed .
Local palette-sparsification conjecture. The graph is -colorable with high probability.
The source describes this as a further suspected extension that removes the global maximum-degree palette size and uses the natural local threshold. No resolution is given, so it remains open.
Sources & referencesView supporting material
Primary source
Jeff Kahn and Charles Kenney, “Asymptotics for Palette Sparsification”, arXiv:2306.00171 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.