The Mapmaker's dilemma (Q1182308): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:00, 30 January 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