Circular choosability of planar graphs

Definitions and mathematical statement

For positive integers $p,q$, a circular $(p,q)$-coloring of a finite simple graph $G$ is a map $c:V(G)\to\{0,1,\ldots,p-1\}$ for which \[ q\le |c(u)-c(v)|\le p-q\qquad(uv\in E(G)). \] This says that the cyclic distance between adjacent colors is at least $q$. A list assignment for this palette gives each vertex a subset $L(v)\subseteq\{0,\ldots,p-1\}$; a list coloring must additionally satisfy $c(v)\in L(v)$.

For a real number $t\ge1$, call $G$ circularly $t$-choosable if, for every pair of positive integers $p,q$ and every list assignment with $|L(v)|\ge tq$ at every vertex, a circular $(p,q)$-list-coloring exists. Since list sizes are integral this means at least $\lceil tq\rceil$ colors. If the palette is too small to admit the specified lists, that pair imposes no condition. Define the circular choice number by \[ \operatorname{cch}(G)=\inf\{t\ge1:G\text{ is circularly }t\text{-choosable}\}. \] The problem is to determine the exact value of $\sup_G\operatorname{cch}(G)$ over all finite planar graphs. A solution requires a universal upper bound and matching examples or a sequence approaching that bound. Planarity refers to existence of a crossing-free drawing, and no particular embedding enters the lists. The quantifiers over palettes and individual lists are essential: this is more restrictive than ordinary circular colorability.

Short English statement

Determine the largest possible circular list-coloring requirement among all finite planar graphs.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3211 (OPG-37619), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Circular choosability of planar graphs. Original problem and discussion. http://www.openproblemgarden.org/op/circular_choosability_of_planar_graphs.