The complexity of coloring games on perfect graphs (Q1202928): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(92)90254-d / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069107705 / rank | |||
Normal rank |
Latest revision as of 11:58, 30 July 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