The Mapmaker's dilemma (Q1182308)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The Mapmaker's dilemma |
scientific article; zbMATH DE number 30809
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The Mapmaker's dilemma |
scientific article; zbMATH DE number 30809 |
Statements
The Mapmaker's dilemma (English)
0 references
28 June 1992
0 references
New type of game with two players, named the Mapmaker and the Explorer, is considered. The Mapmaker tries to colour \(n\) vertices of a \(k\)- colourable graph, while the Explorer reveals more and more of the graph; the Explorer wins if he can force the Mapmaker to change his mind many times. There is shown that for \(3\leq k\leq n\) the Explorer has a winning strategy. The Mapmaker has a winning strategy for \(k=2\). Applications to NP complexity, recursive graph theory and some open problems are given.
0 references
graph colouring
0 references
game with two players
0 references
0 references
0.80254954
0 references
0 references
