Bounding the on-line choice number in terms of the choice number

Bounding the on-line choice number in terms of the choice number

Definitions and mathematical statement

For a finite simple graph $G$, its choice number $\operatorname{ch}(G)$ is the least $k$ such that every assignment of $k$ permitted colours per vertex admits a proper colouring from those lists.

Define the online version through the following finite game. Initially every vertex is uncoloured and has $k$ tokens. In each round Lister marks a nonempty subset $M$ of the uncoloured vertices and removes one token from each marked vertex. Painter then selects an independent subset $I\subseteq M$ and permanently colours those vertices with the fresh colour assigned to that round. If any vertex remains uncoloured with zero tokens after Painter's response, Lister wins. Painter wins if all vertices become coloured. Strategies may depend on the complete history; neither player sees the other's future decisions.

The online choice number $\operatorname{ch}^{\mathrm{OL}}(G)$ is the least $k$ for which Painter has a winning strategy against every play by Lister. The independent-set requirement guarantees a proper colouring because different rounds use different colours. This is also called the paint number.

The source question is whether the additive gap is unbounded: \[ \forall b\in\mathbb N\ \exists\text{ a finite simple graph }G: \quad\operatorname{ch}^{\mathrm{OL}}(G)-\operatorname{ch}(G)\ge b. \] The graph may depend on $b$. A negative answer would give a single absolute additive bound valid for all graphs. This question asks about the difference, not whether the online parameter is bounded by some arbitrary function of the offline parameter.

Short English statement

Can the online list-colouring requirement exceed the ordinary choice number by an arbitrarily large additive amount?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature correction and independent scope.

The historical question in [S2] was answered affirmatively by Duraj, Gutowski and Kozik in 2016 [R1]. Their published result gives an unbounded additive gap already on balanced complete bipartite graphs; it is not merely a bound for a fractional or different online parameter. The retained catalogue "open" metadata is therefore historical. This attempt proves a useful online strategy and an exact obstruction to amplifying a finite example by disjoint unions. It does not claim a new solution or independently reproduce the paper's difficult lower bound for the paint number.

Checking the implication from the published estimates.

Writing $p(N)$ and $c(N)$ for the paint and choice numbers of $K_{N,N}$, the paper proves $p(N)=\log_2N+O(1)$ and derives $c(N)\le\log_2N-(\tfrac12+o(1))\log_2\log_2N$. Subtracting gives $p(N)-c(N)\to\infty$, which has exactly the quantifier order requested: for each fixed integer $b$, some sufficiently large $N$ yields a gap at least $b$. These are explicitly external theorem inputs, not estimates inferred from numerical data or from the leading equivalence $c(N)\sim\log_2N$. That leading equivalence alone would not imply any growing difference.

A self-contained online upper strategy.

More generally let $G$ be any bipartite graph on $N$ vertices, with parts $X,Y$, and give each vertex $k$ tokens, where $N2^{-k}<1$. For every uncoloured vertex with $t$ tokens remaining, assign weight $2^{-t}$. Let $W$ be the sum of those weights. Initially $W=N2^{-k}<1$.

In a round, let $U$ be the total old weight of marked vertices in $X$, and $V$ the corresponding total in $Y$. Their weights double when Lister removes a token. Painter colours all marked vertices in the part with greater old weight, breaking ties arbitrarily. This is an independent set. If $U\ge V$, the change in total weight is \[ (U+V)-2U=V-U\le0; \] the other case is symmetric. Hence after every response $W<1$. An uncoloured vertex with zero tokens would contribute weight one, which is impossible. Lister therefore cannot win.

The play also cannot continue forever without colouring all vertices. Each nonterminal round removes at least one token, and surviving uncoloured vertices cannot exhaust their tokens. There are finitely many initial tokens. Thus the strategy is winning and proves \[ \operatorname{ch}^{\mathrm{OL}}(G) \le\lfloor\log_2N\rfloor+1 \quad\text{for every nonempty bipartite }G. \] For $K_{N,N}$, replacing the total order by $2N$ gives an upper bound $\log_2N+O(1)$, agreeing with the upper side of the cited asymptotic theorem. It supplies no corresponding lower bound against all possible Painter strategies.

Why separate copies cannot amplify an additive gap.

If $G$ is the disjoint union of graphs $G_1,\ldots,G_s$, then \[ \operatorname{ch}(G)=\max_i\operatorname{ch}(G_i),\qquad \operatorname{ch}^{\mathrm{OL}}(G)= \max_i\operatorname{ch}^{\mathrm{OL}}(G_i). \] For the offline statement, colour each component from its lists separately; the reverse inequality follows by restriction. Online, run a winning strategy independently in each component whenever that component receives at least one marked vertex. The union of their responses is independent, and each component sees a legal subsequence of rounds with exactly its own token decrements. Conversely Lister may mark vertices only in one chosen component, reproducing any winning play there. This proves both equalities without assuming that different components must be assigned disjoint palettes.

In particular, taking many copies of a graph with gap one preserves its two parameters and keeps gap one. A proof of unboundedness must change the internal structure or use a family whose quantitative estimates separate; increasing the number of independent copies does not suffice.

Verification and final status.

The weight invariant is checked after Painter's response, matching the zero-token rule in the canonical definition. All marked vertices on the selected side may be coloured together even when the graph is not complete bipartite. The strict initial inequality prevents equality at weight one. Independent full derivation: UNRESOLVED. The precise missing component here is the growing lower separation between the online and offline parameters. The catalogue question itself is already answered affirmatively by [R1], whose result and attribution must not be replaced by an open-status claim.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3248 (OPG-48583), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Bounding the on-line choice number in terms of the choice number. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/bounding_the_on_line_choice_number_in_terms_of_the_choice_number.

• R1 Lech Duraj, Grzegorz Gutowski and Jakub Kozik, Chip games and paintability, Electronic Journal of Combinatorics 23$3$ $2016$, P3.3. Published primary paper, Theorem 1 and Corollary 2 checked 2 October 2026. https://www.combinatorics.org/ojs/index.php/eljc/article/download/v23i3p3/pdf/.