The complexity of coloring games on perfect graphs
type: Item
instance of: scholarly article
title: The complexity of coloring games on perfect graphs
zbMATH Open document ID: 0785.90119
DOI: 10.1016/0304-3975(92)90254-D
author: Hans L. Bodlaender
author: Dieter Kratsch
published in: Theoretical Computer Science
publication date: 1993-04-22T00:00:00Z
review text: This paper addresses the complexity of deciding which of the players has a winning strategy, for the following type of game: two players must color the vertices of a given graph, in a prescribed order, in such a way that no vertex is colored with a color already given to an adjacent vertex. In one variant of this type of game, the first player that is unable to move loses. In the other variant, the first player wins, iff the game ends with the entire graph colored. The paper studies the problem, when the input graphs are restricted, either to interval graphs, split graphs, or bipartite graphs. For interval graphs, it is shown that for certain orderings of the vertices, a `greedy like' strategy gives optimal play for the second game variant; this gives a polynomial time algorithm to decide which player has a winning strategy. The other results in the paper consist of several NP-hardness, coNP-hardness, and PSPACE-completeness results.
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 109472
zbMATH Keywords: coloring games
zbMATH Keywords: perfect graphs
zbMATH Keywords: greedy-like strategy
zbMATH Keywords: winning strategy
zbMATH Keywords: interval graphs
zbMATH Keywords: split graphs
zbMATH Keywords: bipartite graphs
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: NP-hardness
zbMATH Keywords: coNP-hardness
zbMATH Keywords: PSPACE-completeness
Wikidata QID: Q59568011
MaRDI profile type: Publication
cites work: Q4099676
cites work: ON THE COMPLEXITY OF SOME COLORING GAMES
cites work: PSPACE-Hardness of some combinatorial games
cites work: Complexity of problems in games, graphs and algebraic equations
cites work: Q4198056
cites work: Q3328583
cites work: The NP-completeness column: an ongoing guide
cites work: Planar Formulae and Their Uses
cites work: Q3219752
cites work: Hex ist Pspace-vollständig. (Hex is Pspace-complete)
cites work: On the complexity of some two-person perfect-information games
cites work: Design and implementation of an efficient priority queue
full work available at URL: 0304-3975(92)90254-d
OpenAlex ID: W2069107705
DBLP publication ID: journals/tcs/BodlaenderK92
description: scientific article; zbMATH DE number 109472