The authors examine the problem of coloring a subgraph of a k-colorable graph without knowing the entire graph. The present results are phrased in terms of a game with two players: (a)the Mapmaker, who must color a fixed set X of vertices in a manner extendible to a k-coloring of the entire graph, and (b)the Explorer, who adds vertices and edges to the graph, hoping to force the Mapmaker to change his mind many times about how to color X. They show that if k≥3, then the Explorer can force an exponential number of mind-changes; but if k=2, then she can only force a linear number of mind-changes. Applications to recursive graph theory are given.
