Multiple Circular Colouring as a Model for Scheduling

Bing Zhou

Department of Mathematics, Trent University, Peterborough, Canada.

DOI: 10.4236/ojdm.2013.33029                

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.

Keywords

Graph Coloring; Circular Chromatic Number; Fractional Chromatic Number; Multi-Circular Coloring; Scheduling Problem

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	V. C. Barbosa and E. Gafni, “Concurrency in Heavily Loaded Neighborhood-Constrained Systems,” ACM Transactions on Programming Languages and Systems, Vol. 11, No. 4, 1989, pp. 562-584. doi:10.1145/69558.69560
[2]	H. G. Yeh, “A Connection between Circular Colorin and Periodic Schedules,” Discrete Applied Mathematics, Vol. 157, No. 7, 2009, pp. 1663-1668. doi:10.1016/j.dam.2008.10.003
[3]	H. G. Yeh and X. Zhu, “Resource-Sharing System Scheduling and Circular Chromatic Number,” Theoretical Computer Science, Vol. 332, No. 1-3, 2005, pp. 447-460. doi:10.1016/j.tcs.2004.12.005
[4]	F. Chung, “Graph Theory in the Information Age,” Notices of AMS, Vol. 57, No. 6, 2010, pp. 726-732.
[5]	A. Vince, “Star Chromatic Number,” Journal of Graph Theory, Vol. 12, No. 4, 1988, pp. 551-559. doi:10.1002/jgt.3190120411
[6]	H. L. Abbott and B. Zhou, “The Star Chromatic Number of a Graph,” Journal of Graph Theory, Vol. 17, No. 3, 1993, pp. 349-360. doi:10.1002/jgt.3190170309
[7]	H. Hatami and R. Tusserkani, “On the Complexity of the Circular Chromatic Number,” Journal of Graph Theory, Vol. 47, No. 3, 2004, pp. 226-230. doi:10.1002/jgt.20022
[8]	K. Kilakos and B. Reed, “Fractionally Colouring Total Graphs,” Combinatorica, Vol. 13, No. 4, 1993, pp. 435-440. doi:10.1007/BF01303515
[9]	D. Kral, E. Macajova and J.-S. Sereni, “Circular Edge-Coloring of Cubic Graphs with Girth Six,” Journal of Combinatorial Theory, Series B, Vol. 100, No. 4, 2010, pp. 351-358. doi:10.1016/j.jctb.2009.10.003
[10]	I. Leader, “The Fractional Chromatic Number of Infinite Graphs,” Journal of Graph Theory, Vol. 20, No. 4, 1995, pp. 411-418. doi:10.1002/jgt.3190200404
[11]	B. Zhou, “Some Theorems Concerning the Star Chromatic Number of a Graph,” Journal of Combinatorial Theory, Series B, Vol. 70, No. 2, 1997, pp. 245-258. doi:10.1006/jctb.1996.1738
[12]	E. R. Scheinerman and D. H. Ullman, “Frational Graph Theory,” John Wiley and Sons, New York, 1997.
[13]	X. Zhu, “Circular Chromatic Number—A Survey,” Discrete Mathematics, Vol. 229, No. 1-3, 2001, pp. 371-410. doi:10.1016/S0012-365X(00)00217-X
[14]	X. Zhu, “Recent Developments in Circular Colouring of Graphs,” Algorithms and Combinatorics, Vol. 26, Springer, Berlin, Heidelberg, 2006, pp. 497-550.
[15]	M. Knser, “Aufgabe 300,” Jahresbericht der Deutsche Mathematiker-Vereinigung, Vol. 58, No. 2, 1955, p. 27.
[16]	L. Lovasz, “Kneser’s Conjecture, Chromatic Number, and Homotopy,” Journal of Combinatorial Theory, Series A, Vol. 25, No. 3, 1978, pp. 319-324. doi:10.1016/0097-3165(78)90022-5
[17]	M. Lasen, J. Propp and D. H. Ullman, “The Fractional Chromatic Number of Mycielski Graphs,” Journal of Graph Theory, Vol. 19, No. 3, 1995, pp. 411-416. doi:10.1002/jgt.3190190313
[18]	G. Chang, “Circular Chromatic Numbers of Mycielski’s Graphs,” Discrete Mathematics, Vol. 205, No. 1-3, 205, 1999, pp. 23-37. doi:10.1016/S0012-365X(99)00033-3
[19]	H. Jajiaholhassan and X. Zhu, “Circular Chromatic Number and Mycielski Construction,” Journal of Graph Theory, Vol. 44, No. 2, 2003, pp. 106-115. doi:10.1002/jgt.10128