Eternal chromatic number
Abstract
Graph coloring has long been recognized as an appropriate model for allocating scarce resources to competing users, such as class time slots at universities. Here two classes that might share an instructor or student should be scheduled at different times. A problem that does not seem to be addressed in scheduling models is the inevitable request, perhaps by an unhappy professor, to change a class's time of offering after the schedule has been set. The scheduler^ dilemma is to accommodate legitimate requests without unduly modifying, by the potential ripple effect, the overall schedule. In this paper, we address this problem by investigating a special class of colorings. In each member of the class and for each vertex ν, a new coloring in the class can be obtained which changes the color of ν and any other changes are limited to the neighborhood of ν. Such colorings are called eternal.
