27
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ I think you may be able to model this as an Ehrenfeucht–Fraïssé game. $\endgroup$
    – Tyson Williams
    Commented Jul 21, 2012 at 3:52
  • 1
    $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Jul 22, 2012 at 2:19
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 24, 2012 at 11:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yuval Filmus
    Commented Jul 24, 2012 at 12:55
  • $\begingroup$ @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. $\endgroup$
    – Yuval Filmus
    Commented Jul 24, 2012 at 12:57

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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