Separation-number conjecture for complete graphs

Let KnK_n be the complete graph, and let sep(Kn,a,b)\mathsf{sep}(K_n,a,b) denote its separation threshold for aa-list assignments and bb-fold colorings. Let n4n\geq 4, let a,ba,b be the list and coloring parameters, and let pp satisfy

2pn2,pba<(p+1)b.2\leq p\leq n-2,\qquad pb\leq a<(p+1)b.

Separation-number conjecture. Under these conditions,

sep(Kn,a,b)=2pap(p+1)bn1+ϵ,ϵ{1,0}.\mathsf{sep}(K_n,a,b)=\left\lceil\frac{2pa-p(p+1)b}{n-1}\right\rceil+\epsilon,\qquad \epsilon\in\{-1,0\}.

The conjecture combines the partial results preceding it and predicts the separation threshold across the intermediate ranges of a/ba/b. The supplied text presents it as unresolved; the correction term ϵ\epsilon may depend on a,b,na,b,n.

Sources & referencesView supporting material

Primary source

Jean-Christophe Godin, Rémi Grisot and Olivier Togni, “On List Coloring with Separation of the Complete Graph and Set System Intersections”, arXiv:2209.03436 (2022).

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.