The Mapmaker's dilemma (Q1182308): Difference between revisions

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.