Scientific talk by Nicolas de Almeide Martins (COATI team)
Recent Results in Graph Coloring Games
Abstract: The graph coloring game was first introduced, in the context of graph theory, by Bodlaender in 1991. In such a game there are two players, Alice and Bob. The players are given a graph G and a set of colors C={1,2,…,k}. Starting with Alice, each player, alternately, must choose a vertex v and a color in C to apply to v. The colored vertices must always induce a proper coloring of G. Alice wins if all vertices are colored and Bob wins otherwise. The minimum k such that Alice has a winning strategy with k colors is called the game chromatic number of a graph, denoted by 𝛘_g(G). Boblaender mentioned that the complexity of such a game was an interesting open question.
Recently, Costa et al. proved that, given a k, deciding if 𝛘_g(G) ≤ k is PSPACE-complete, answering the question left open by Bodlaender. After this result, a number of variations of the coloring game were also proved to be PSPACE-complete. In this seminar, we shall present these recent results and introduce a new variation for which the complexity is still an open problem.
When: Monday, Feb 19 at 2pm
Where: Euler Violet
