Palette-sparsification conjecture at the local degree threshold

Let GG be a graph on vertex set VV with degree dvd_v at each vertex vv. Let Γ\Gamma be an arbitrary color set, let SvΓS_v\subseteq\Gamma satisfy Sv=dv+1|S_v|=d_v+1 for every vVv\in V, and let each LvL_v be a uniformly random \ell-subset of SvS_v, where

=(1+ε)logn\ell=(1+\varepsilon)\log n

for fixed ε>0\varepsilon>0.

Local palette-sparsification conjecture. The graph GG is LL-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

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.