On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles

Rafayel R. Kamalian

Institute for Informatics and Automation Problems, The National Academy of Sciences of Republic of Armenia,Yerevan, Republic of Armenia.

DOI: 10.4236/ojdm.2013.31009                

Abstract

A proper edge t-coloring of a graph G is a coloring of its edges with colors 1,2,???,t such that all colors are used, and no two adjacent edges receive the same color. A cyclically interval t-coloring of a graph G is a proper edge t-coloring of G such that for each its vertex x, either the set of colors used on edges incident to x or the set of colors not used on edges incident to x forms an interval of integers. For an arbitrary simple cycle, all possible values of t are found, for which the graph has a cyclically interval t-coloring.

Keywords

Proper Edge Coloring; Cyclically Interval Coloring; Simple Cycle

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. B. West, “Introduction to Graph Theory,” Prentice-Hall, Upper Saddle River, 1996.
[2]	V. G. Vizing, “The Chromatic Index of a Multigraph,” Kibernetika, Vol. 3, 1965, pp. 29-39.
[3]	A. S. Asratian and R. R. Kamalian, “Interval Colorings of Edges of a Multigraph,” Applied Mathematics, Vol. 5, Yerevan State University, 1987, pp. 25-34. (in Russian)
[4]	A. S. Asratian and R. R. Kamalian, “Investigation of Interval Edge-Colorings of Graphs,” Journal of Combinatorial Theory, Series B, Vol. 62, No. 1, 1994, pp. 34-43. doi:10.1006/jctb.1994.1053
[5]	R. R. Kamalian, “Interval Edge Colorings of Graphs,” Doctoral Dissertation, The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990. (in Russian)
[6]	R. R. Kamalian, “Interval Colorings of Complete Bipartite Graphs and Trees,” Preprint of the Computing Centre of the Academy of Sciences of Armenia, 1989. (in Russian)
[7]	R. R. Kamalian, “On a Number of Colors in Cyclically Interval Edge Colorings of Trees,” Research Report LiTH-MAT-R-2010/09-SE, Linkoping University, 2010.
[8]	R. R. Kamalian, “On Cyclically-Interval Edge Colorings of Trees,” Buletinul Academiei de Stiinte a Republicii Moldova Matematica, Vol. 68, No. 1, 2012, pp. 50-58.
[9]	A. Kotzig, “1-Factorizations of Cartesian Products of Regular Graphs,” Journal of Graph Theory, Vol. 3, No. 1, 1979, pp. 23-34. doi:10.1002/jgt.3190030104
[10]	J. J. Bartholdi, J. B. Orlin and H. D. Ratliff, “Cyclic Scheduling via Integer Programs with Circular Ones,” Operations Research, Vol. 28, No. 5, 1980, pp. 1074-1085. doi:10.1287/opre.28.5.1074
[11]	W. Dauscha, H. D. Modrow and A. Neumann, “On Cyclic Sequence Type for Constructing Cyclic Schedules,” Zeitschrift für Operations Research, Vol. 29, No. 1, 1985, pp. 1-30.
[12]	D. de Werra, N. V. R. Mahadev and P. Solot, “Periodic Compact Scheduling,” ORWP 89/18, Ecole Polytechnique Fédérale de Lausanne, 1989.
[13]	D. de Werra and Ph. Solot, “Compact Cylindrical Chromatic Scheduling,” ORWP 89/10, Ecole Polytechnique Fédérale de Lausanne, 1989.
[14]	R. R. Kamalian, “On Cyclically Continuous Edge Colorings of Simple Cycles,” Proceedings of the Computer Science and Information Technologies Conference, Yerevan, 24-28 September 2007, pp. 79-80. (in Russian)