Title

Eternal Chromatic Number

Keywords

Chromatic number; Eternal security; Graph characterization; Graph coloring; Scheduling

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.

Publication Date

1-1-2014

Publication Title

Utilitas Mathematica

Volume

94

Number of Pages

287-302

Document Type

Article

Personal Identifier

scopus

Socpus ID

84903167551 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84903167551

This document is currently not available here.

Share

COinS