Title

ETERNAL CHROMATIC NUMBER

Authors

Authors

M. Anderson; R. Brigham; R. D. Dutton;R. Vitray

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Util. Math.

Keywords

chromatic number; eternal security; graph characterization; graph; coloring; scheduling; Mathematics, Applied; Statistics & Probability

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's 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 v, a new coloring in the class can be obtained which changes the color of v and any other changes are limited to the neighborhood of v. Such colorings are called eternal.

Journal Title

Utilitas Mathematica

Volume

94

Publication Date

1-1-2014

Document Type

Article

Language

English

First Page

287

Last Page

302

WOS Identifier

WOS:000339457700017

ISSN

0315-3681

Share

COinS