Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

1 Answer 1

up vote 6 down vote accepted

It looks fairly similar to

Coloring random graphs online without creating monochromatic subgraphs (Reto Spöhel, Torsten Mütze, and Thomas Rast) Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.


share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.