Back
 OJDM  Vol.3 No.1 , January 2013
On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles
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.
Cite this paper: R. Kamalian, "On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 43-48. doi: 10.4236/ojdm.2013.31009.
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)

 
 
Top