The Mapmaker's dilemma (Q1182308): Difference between revisions
From MaRDI portal
Latest revision as of 10:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Mapmaker's dilemma |
scientific article |
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