ETERNAL CHROMATIC NUMBER

    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