Authors: Richard Beigel and William Gasarch
Abstract: We examine the problem of coloring part of a k-colorable graph, while not knowing the rest of it. To illustrate some of our concepts, we describe a somewhat whimsical scenario, which we call the Mapmaker's Dilemma.
Picture a 12th-century mapmaker who is given a map of Europe and the countries adjacent to Europe, and is told to 4-color the European countries in a manner that is consistent with some coloring of the entire world. Unfortunately, Asia has not yet been explored. He cannot expect to find a consistent coloring given incomplete information, but the people must have their maps colored, so he colors Europe based on the information at hand. The world is small, and he does not have anything else to do, so this takes negligible time. From time to time, he receive reports from explorers of newly discovered countries and their neighbors. (This is a relatively peaceful time, so countries and borders do not disappear from the map.) This new information may invalidate his 4-coloring of Europe, so that he has to recolor it, at great cost to his publisher. Four-color photocopying is a novelty that few can afford; therefore he hopes, through some cleverness, to minimize the number of times he has to recolor the map of Europe.
We study a problem similar to that of the mapmaker. In particular, we study the problem of coloring a subgraph H of a k-colorable graph G, where G is given to us only a little at a time.