Minimum-Degree Lower Bounds for Game Chromatic Index

Definitions and mathematical statement

Let $G$ be a finite simple graph and let $\delta(G)=\min_{v\in V(G)}d_G(v)$. In a standard edge-coloring game with a fixed palette of $q$ colors, Alice and Bob alternately color one previously uncolored edge while maintaining a proper edge coloring: incident edges must have different colors. Alice seeks to have every edge colored and Bob seeks to prevent completion. Under an Alice-first, no-pass convention, the game chromatic index $\chi'_g(G)$ is the least $q$ for which Alice has a winning strategy against every legal Bob play. The source does not specify the player-order or passing conventions, so the exact variant must be confirmed.

The extracted conjecture is \[ \exists\varepsilon>0\quad\exists d_0\in{\mathbb{Z}}_{\geq1}\quad \forall G\text{ finite simple},\qquad \delta(G)\geq d_0\ \Longrightarrow\ \chi'_g(G)\geq(1+\varepsilon)\delta(G). \] The same positive $\varepsilon$ and threshold $d_0$ must work for all graphs, independent of their order and degree sequence. The degree in the bound is minimum degree, not maximum degree, and no regularity or bipartiteness restriction is present. The question seeks a fixed multiplicative gap above minimum degree for all sufficiently high-minimum-degree graphs, not an additive lower bound or an example family only.

The supplied literature assessment checked 2026-08-21 says that the extracted minimum-degree question is incomplete and remains unresolved in its checked formulation. The cleaned record gives the displayed numerical quantifiers but still lacks the game variant. No additional missing hypothesis or precise theorem is reproduced, so a different coloring-game convention or an unstated graph class is not supplied from inference.

Short English statement

Is the game chromatic index always at least a fixed factor greater than minimum degree once that degree is sufficiently large? The constants must be universal over graphs; the exact edge-coloring-game convention still needs confirmation.

Sources

• Local UnsolvedMath registry, permanent ID 30000738, catalogue entry, Minimum-Degree Lower Bounds for Game Chromatic Index.
• Mini-Workshop: Positional Games (2008), Oberwolfach Reports, pp. 1073--1114, DOI https://doi.org/10.4171/owr/2007/20.
• Supplied reference "game chromatic index open questions": https://www.combinatorics.org/ojs/index.php/eljc/article/download/v25i2p33/pdf/.
• Supplied source-verification claim and literature triage checked 2026-08-21; no complete game-rule convention or exact later theorem is reproduced.