<p>It looks fairly similar to </p>

<blockquote>
  <p>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.</p>
</blockquote>

<ul>
<li><a href="http://sigma.ict.ac.cn/seminar/web/archive/soda2011/SODA11_013_muetzet.pdf" rel="nofollow">SODA PDF</a></li>
<li><a href="http://onlinelibrary.wiley.com/doi/10.1002/rsa.20445/abstract" rel="nofollow">Journal version</a></li>
<li><a href="http://epubs.siam.org/doi/abs/10.1137/1.9781611973082.13" rel="nofollow">Conference proceedings</a></li>
</ul>

CC BY-SA 3.0
2012-11-22T13:50:50.760Z
2014-10-01T01:20:23.030Z
2014-10-01T01:20:23.030Z
adrianN
<p>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)$.</p>

<p>Is this game known?</p>

CC BY-SA 3.0
2012-07-21T03:52:54.960Z
I think you may be able to model this as an [Ehrenfeucht–Fraïssé game](http://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9_game).
Tyson Williams
CC BY-SA 3.0
2012-07-22T02:19:28.113Z
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
CC BY-SA 3.0
2012-07-24T11:58:25.510Z
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
CC BY-SA 3.0
2012-07-24T12:55:49.790Z
@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
CC BY-SA 3.0
2012-07-24T12:57:22.677Z
@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
<reference-request><graph-theory><co.combinatorics><graph-colouring><decision-trees>
Coloring complexity of graphs
Yuval Filmus
# Coloring complexity of graphs

(Asked by: username_0 on 2012-07-20)

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?

**Tags:** reference-request, graph-theory, co.combinatorics, graph-colouring, decision-trees
> **Comments:**
> **username_1**: I think you may be able to model this as an [Ehrenfeucht–Fraïssé game](http://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9_game).  
> **username_2**: 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  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_4 on 2012-11-22. Score: 11 | Accepted answer

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.

* [SODA PDF](http://sigma.ict.ac.cn/seminar/web/archive/soda2011/SODA11_013_muetzet.pdf)
* [Journal version](http://onlinelibrary.wiley.com/doi/10.1002/rsa.20445/abstract)
* [Conference proceedings](http://epubs.siam.org/doi/abs/10.1137/1.9781611973082.13)


---

