Unimodality conjecture for the choice–chromatic gap

Let \jump(g,r)\jump(g,r) be the maximum choice–chromatic gap among graphs embeddable on the orientable surface of genus gg with chromatic number rr, and let H(g)H(g) be the maximum chromatic number of a graph embeddable on that surface. Unimodality conjecture. For each fixed gg, the function \jump(g,r)\jump(g,r) is unimodal in rr: there exists r0=r0(g)r_0=r_0(g) such that

\jump(g,1)\jump(g,2)\jump(g,r0)\jump(g,H(g)).\jump(g,1)\leq\jump(g,2)\leq\dotsb\leq\jump(g,r_0)\geq\dotsb\geq\jump(g,H(g)).

The conjecture is known for planar and toroidal graphs, and the source notes that unimodality also holds for the projective plane and Klein bottle; the general orientable-surface case remains open.

Sources & referencesView supporting material

Primary source

Niranjan Balachandran and Brahadeesh Sankarnarayanan, “The choice number versus the chromatic number for graphs embeddable on orientable surfaces”, arXiv:2102.06993 (2021).

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.