The complexity of coloring games on perfect graphs (Q1202928): Difference between revisions
From MaRDI portal
Revision as of 14:28, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity of coloring games on perfect graphs |
scientific article |
Statements
The complexity of coloring games on perfect graphs (English)
0 references
22 April 1993
0 references
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.
0 references
coloring games
0 references
perfect graphs
0 references
greedy-like strategy
0 references
winning strategy
0 references
interval graphs
0 references
split graphs
0 references
bipartite graphs
0 references
polynomial time algorithm
0 references
NP-hardness
0 references
coNP-hardness
0 references
PSPACE-completeness
0 references