Greedy play can require more colors in the coloring game

In the coloring game, Alice and Bob alternately color vertices properly from a fixed palette, with Alice trying to color the whole graph. The game chromatic number is the least palette size for which she can win. In the greedy game the players choose vertices, each receiving the least available positive integer; Alice minimizes and Bob maximizes the number of colors used. Havet and Zhu asked in June 2011 whether the resulting game Grundy number is always at most the game chromatic number. We give an explicit finite simple graph $G$ for which $\chi_g(G)=5$ and $\Gamma_g(G)=6$, answering the first part of their question negatively. The proof consists of finite strategy certificates checked by two separately written certificate checkers for the two unrestricted Alice-first games, together with a clique obstruction and a short greedy strategy. It does not establish arbitrarily large separation between the parameters. This work has not yet been reviewed by experts. The proofs, the search code, the certificate checkers and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction.

Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.