Sub-Twice-Maximum-Degree Game Chromatic Index Bounds

Definitions and mathematical statement

For the usual finite simple graph convention, let $\Delta(G)=\max_{v\in V(G)}\deg_G(v)$. In the standard proper edge-coloring game with a palette of $q$ colors, Alice and Bob alternately color a previously uncolored edge, keeping incident edges differently colored. Alice seeks a complete edge coloring, while Bob seeks to prevent completion. The game chromatic index $\chi'_g(G)$ is the least $q$ for which Alice has a winning strategy against every legal Bob strategy, with the specified starting-player and move conventions. The source names this invariant without spelling out those conventions, so the usual Alice-first interpretation is made explicit rather than claimed uniquely determined.

The conjecture asks for one absolute constant $\varepsilon>0$ such that \[ \forall G\text{ nonempty in the intended graph class},\qquad \chi'_g(G)\leq(2-\varepsilon)\Delta(G). \] The constant must be chosen before the graph and cannot depend on its maximum degree, order or structure. Equivalently, within a fixed positive-degree graph class, the ratios $\chi'_g(G)/\Delta(G)$ should be uniformly bounded away from $2$. The statement includes all allowed degrees, not just sufficiently large ones, and has no additive constant. A bound $2\Delta(G)-o(\Delta(G))$ or $(2-\varepsilon_G)\Delta(G)$ with graph-dependent $\varepsilon_G$ would be weaker.

Nonempty might mean at least one edge or merely at least one vertex. In the latter case, edgeless graphs need the convention $\chi'_g=\Delta=0$, and the ratio formulation is restricted to positive maximum degree. The source also does not specify finite/simple versus multigraphs, the treatment of passes, or a different starting player; these can affect the game invariant. No change of the graph class or game rules is silently made to obtain the bound.

The literature triage checked 2026-08-21 says the actual conjecture was omitted by extraction and conservatively retains an open fragment. That description conflicts with both current statement fields, which explicitly give the uniform $\varepsilon$ inequality. It does not supply a current status assessment for the completed question. The open label and reported official-source verification remain dated metadata, not independently checked conclusions.

Short English statement

Is the game chromatic index uniformly less than twice maximum degree by one absolute positive fraction, for every intended nonempty graph? The same $\varepsilon$ must work for all graphs and all degrees, with no additive term. The exact edge-coloring-game and graph conventions remain to be confirmed.

Sources

• Local UnsolvedMath registry, permanent ID 30000736, source code catalogue entry, "Sub-Twice-Maximum-Degree Game Chromatic Index Bounds," including both explicit uniform-gap statements and the conflicting extraction assessment.
• 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.