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

Author(s)
Rafayel R. Kamalian

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.

A proper edge

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.

R. Kamalian, "On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles,"

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)

[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)