Thresholds in Multicolor Online Graph-Coloring Games

Definitions and mathematical statement

The record contains three online graph-coloring questions. In the usual Ramsey-type online setting, Painter assigns an irrevocable color to each arriving vertex or edge, seeking to avoid a monochromatic copy of a specified graph $F$. This is distinct from requiring a proper coloring unless that is the chosen forbidden-pattern objective. The arrival mechanism, adversarial versus random model, information revealed and threshold parameter are not defined in the supplied record; this conventional description is therefore conditional.

1. Extend the stated two-color threshold theorem to every integer $r\geq2$. The cleaned statement specifically names online edge-coloring games, whereas the original refers to a vertex/edge-coloring threshold theorem. Both vertex and edge contexts are retained as source scope, without claiming a common threshold formula. The two-color theorem itself and its hypotheses are absent, so no density or random-graph threshold is guessed.
2. Determine whether the known lower-bound expression is the correct threshold. The clean version asks this for trees $F$, while the original asks about every vertex-coloring game and explicitly says the lower bound is based on $m_1(F)$. Neither $m_1$ nor the expression is supplied. Thus the tree question and the broader original vertex-game question are recorded separately; the latter is not silently discarded or declared equivalent to the former.
3. Determine thresholds in the balanced variant, for both vertex and edge arrivals, where Painter receives a batch of $r$ objects at each step and must use each of the $r$ colors exactly once within that batch. Formally the coloring of each complete batch is a bijection onto $\{1,\ldots,r\}$, with choices made online under the intended information rules. This is a per-batch constraint, not merely equal final color-class sizes. The treatment of a final incomplete batch and the precise objective remain unspecified.

A definite threshold statement requires a sequence of boards or arrival processes, the variable being tuned, a success/winning event and the mode of transition, such as deterministic winning regions or asymptotically high-probability regimes. None is identified. Thresholds for a fixed $F,r$, their asymptotic order, a leading constant and a sharp-threshold window are different targets; the source does not select one. The symbols and scope from the original cannot be reconstructed by assuming a particular standard density formula for $m_1(F)$.

The literature triage checked 2026-08-21 reports the arbitrary-color and balanced questions open and no complete resolution of the collection located. That does not provide an individual theorem status for each scope above. The open label and reported official-source verification remain dated metadata, especially given the original/cleaned changes in edge/vertex and tree/general wording.

Short English statement

Extend the two-color online threshold results to arbitrary color counts, test the source's missing lower-bound formula, and find thresholds under a one-of-each-color constraint in every batch. The original includes vertex/edge and general vertex-game scopes beyond the clean edge/tree wording; those distinctions are retained. The game process and threshold parameter are undefined.

Sources

• Local UnsolvedMath registry, permanent ID 30000741, source code catalogue entry, "Thresholds in Multicolor Online Graph-Coloring Games," including all three original questions, the $m_1(F)$ reference and the different cleaned edge/tree scope.
• Mini-Workshop: Positional Games (2008), Oberwolfach Reports, pp. 1073--1114, DOI 10.4171/owr/2007/20: https://doi.org/10.4171/owr/2007/20. This is the sole supplied literature reference. The citation uses 2008, while the DOI and proposed-year metadata use 2007.
• Literature triage checked 2026-08-21; record updated 2026-09-16. No external source has been visited or independently checked here.