# Coloring complexity of graphs

Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ for this vertex. The game ends when a monochromatic edge is discovered. Let $X(G)$ be the maximal length of the game under optimal play by both players (Alice wants to shorten the game as possible, Bob wants to delay it as possible). For example, $X(K_n) = n$ and $X(C_{2n+1}) = \Theta(\log n)$.

Is this game known?

• I think you may be able to model this as an Ehrenfeucht–Fraïssé game. – Tyson Williams Jul 21 '12 at 3:52
• it would seem to be highly related to greedy graph coloring algorithms, right? of which there are many.... similarly to SAT problems where one of the variables is "forced" after some DPLL traversal... which I believe is also called the "backbone" in SAT – vzn Jul 22 '12 at 2:19
• Why do you use d−1? I think that it is more natural to parameterize the game by both the graph G and the number k of allowed colors and to consider the analogous quantity X(G, k). Of course, if k≥χ(G), then Bob wins, and therefore in this case, X(G, k) should be defined as either ∞ or n+1. – Tsuyoshi Ito Jul 24 '12 at 11:58
• @Tsuyoshi: $k = d-1$ is an arbitrary choice designed to maximize $X(G)$. In the application I have in mind, $k \geq \chi(G)$ doesn't make sense. – Yuval Filmus Jul 24 '12 at 12:55
• @Tyson: In fact, $X(G)$ is the decision tree complexity of the game in which, given a $d-1$ coloring of $G$, we want to find a violated edge. – Yuval Filmus Jul 24 '12 at 12:57