TITLE:
Multiple Circular Colouring as a Model for Scheduling
AUTHORS:
Bing Zhou
KEYWORDS:
Graph Coloring; Circular Chromatic Number; Fractional Chromatic Number; Multi-Circular Coloring; Scheduling Problem
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.3,
July
12,
2013
ABSTRACT:
In this article we propose a new model for scheduling
periodic tasks. The model is based on a variation of the circular chromatic
number, called the multiple circular colouring of the conflict graph. We show
that for a large class of graphs, this new model will provide better solutions
than the original circular chromatic number. At the same time, it allows us to
avoid the difficulty of implementation when the fractional chromatic number is
used.