gpt 6 astra ultra attempt on Math-600

Monotonicity of the Vertex-Colouring Game

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

In the standard game used here, Alice moves first and the players alternately give an uncoloured vertex one of $k$ colours while maintaining a proper partial colouring. Alice wins if all vertices are eventually coloured; Bob wins if the process reaches a position that cannot be completed by legal play. Ask whether an Alice-winning graph with palette size $k$ must also be Alice-winning with palette size $k+1$. [S1] [S2]

Statement recorded in the supplied source.

If Alice has a winning strategy for the vertex coloring game with k colors, does she have one for k+1 colors? [S1]

Scope and interpretation.

Game conventions matter. This section spells out the standard alternating, Alice-first proper-colouring convention rather than claiming the same implication for every colouring-game variant. [S1]

Short English statement

Can giving both players one extra colour ever turn Alice’s winning vertex-colouring game into a losing one?

Research attempt

Status: UNRESOLVED. We prove monotonicity in some elementary regimes, give an exact game-state recursion, and check all labelled graphs through four vertices. The crucial strategy-transfer step for the extra colour remains unproved.

Rules and literature check.

Hollom [E1], primary abstract checked 1 October 2026, distinguishes the usual game from ordered and connected variants, and does not settle monotonicity for the usual vertex game. We use exactly the unrestricted Alice-first convention in the canonical definition. A vertex with no available colour is permanently blocked: later moves only add colours to its neighborhood. Thus reaching such a vertex is equivalent to an inevitable Bob win, even if some other vertices can still be coloured.

A palette size above maximum degree.

If $k\ge\Delta(G)+1$, every uncoloured vertex always has an available colour: at most $\deg(v)\le\Delta(G)$ different colours appear on its neighbours. This holds after either player's move and for every legal partial colouring. Since each move colours exactly one vertex, the game finishes after $|V(G)|$ moves with a complete proper colouring. Alice therefore wins independently of how either player chooses vertices and colours. In particular the desired implication holds whenever the smaller palette already has more colours than the maximum degree.

This argument uses maximum degree, not degeneracy. A degeneracy ordering supplies an order in which ordinary greedy colouring works, but Bob is free to choose a different next vertex. Treating that ordering as mandatory changes the game.

Complete graphs and the one-colour case.

On $K_r$, fewer than $r$ colours cannot produce a complete proper colouring. After $k<r$ vertices have received distinct colours, every remaining vertex is blocked. With $k\ge r$, the maximum-degree argument applies. Thus Alice wins on $K_r$ exactly when $k\ge r$, and monotonicity follows for this family.

For one colour, Alice wins exactly on edgeless graphs. An edge prevents any complete one-colouring, while an edgeless graph permits every move until completion. Every edgeless graph also wins with two colours. This proves the implication $1\to2$ for all graphs without saying anything about the first difficult larger-palette cases.

Exact recursive decision procedure.

Represent a state by a partial map $s:V\to\{1,\ldots,k\}$ and whose turn it is. Let $W_k(s)$ mean Alice can force completion. If all vertices are coloured, set $W_k(s)=\mathrm{true}$. If an uncoloured vertex sees all $k$ colours, set it to false. Otherwise let $\mathcal M_k(s)$ be the nonempty set of legal next states. Then \[ W_k(s)= \begin{cases} \bigvee_{s'\in\mathcal M_k(s)}W_k(s'),&\text{Alice to move},\\ \bigwedge_{s'\in\mathcal M_k(s)}W_k(s'),&\text{Bob to move}. \end{cases} \] This recursion is justified by backward induction on the number of uncoloured vertices. On Alice's turn one winning move suffices; on Bob's turn every legal move must preserve Alice's win. Each edge in the state tree reduces the number of uncoloured vertices by one, so recursion terminates. Memoization can avoid repeated states but does not make the worst-case number of partial colourings polynomial.

Why the naive extra-colour coupling breaks.

One might run the $k$-colour strategy while ignoring colour $k+1$. Alice can avoid that colour, but Bob need not. Identifying $k+1$ with a fixed old colour can turn a legal position into an illegal one: an edge with endpoint colours $k$ and $k+1$ is proper before identification and monochromatic afterwards. This two-vertex example refutes that particular simulation map, not monotonicity itself.

Similarly, deleting the vertices Bob coloured with the extra colour changes whose turn occurs in the simulated game, and the omitted vertices still forbid colours on their neighbours. A strategy-transfer proof needs an invariant controlling both effects. Inclusion of legal moves alone is insufficient: the larger palette enlarges Bob's choices as well as Alice's, and the recursive universal quantifier at Bob positions makes that distinction explicit.

Executed finite verification.

The local exact checker enumerated all $1+2+8+64=75$ labelled simple graphs of orders one through four. For each order $n$ it evaluated the recursion for every palette $1,\ldots,n+1$, caching exact tuple states. It found no implication failure between consecutive palettes. At $k\ge n$ the maximum-degree theorem already guarantees Alice's win, so larger palettes add no untested case at these orders. The checker treats any blocked vertex as an immediate Bob win and alternates turns by the number of coloured vertices.

The reproducible script and its output are retained in the local audit's root/checks.py and root/checks_results.json. This is a bounded check, not a claim about all graphs or a proof assistant verification. It also provides small cases against which to test any proposed state-space symmetry reduction.

Final gap.

The problem remains unresolved outside the proved classes and finite range. The exact missing lemma is a transformation of an arbitrary Alice-winning $k$-colour strategy into a winning $(k+1)$-colour strategy while handling Bob's new-colour moves. The invalid colour-identification map and the game-state quantifiers explain why ordinary colouring monotonicity does not supply that lemma.

Sources

• E1 L. Hollom, A note on monotonicity in Maker-Breaker graph colouring games, revised 8 November 2024. Primary abstract checked 1 October 2026. https://arxiv.org/abs/2308.03528.

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1392 (GRAPH-005), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Graph coloring game overview. https://en.wikipedia.org/wiki/Graph_coloring_game. Bibliographic information from the supplied record.