Share This Article:

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

Abstract Full-Text HTML XML Download Download as PDF (Size:173KB) PP. 43-48
DOI: 10.4236/ojdm.2013.31009    2,995 Downloads   5,005 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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)

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.