Note on Cyclically Interval Edge Colorings of Simple Cycles

Nannan  Wang; Yongqiang  Zhao

doi:10.4236/ojdm.2016.63016

Nannan Wang¹, Yongqiang Zhao²^*

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 vertex

, 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. In this paper, we provide a new proof of the result on the colors in cyclically interval edge colorings of simple cycles which was first proved by Rafayel R. Kamalian in the paper “On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles, Open Journal of Discrete Mathematics, 2013, 43-48”.

Keywords: Edge Coloring, Interval Edge Coloring, Cyclically Interval Edge Coloring

Cite this paper: Wang, N. and Zhao, Y. (2016) Note on Cyclically Interval Edge Colorings of Simple Cycles. Open Journal of Discrete Mathematics, 6, 180-184. doi: 10.4236/ojdm.2016.63016.

References

[1] Asratian, A.S. and Kamalian, R.R. (1987) Interval Colorings of Edges of a Multigraph. Applied Mathematics, 5, 25-34. (In Russian)

[2] Asratian, A.S. and Kamalian, R.R. (1994) Investigation on Interval Edge-Colorings of Graphs. Journal of Combinatorial Theory, Series B, 62, 34-43.
http://dx.doi.org/10.1006/jctb.1994.1053

[3] Kotzig, A. (1979) 1-Factorizations of Cartesian Products of Regular Graphs. Journal of Graph Theory, 3, 23-34.
http://dx.doi.org/10.1002/jgt.3190030104

[4] Werra, D. and Solot, Ph. (1989) Compact Cylindrical Chromatic Scheduling. ORWP 89/10, Ecole Polytechnique Fédérale de Lausanne.

[5] Kamalian, R.R. (1990) Interval Edge Colorings of Graphs. PhD Dissertation, the Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk. (In Russian)

[6] Kamalian, R.R. (1989) Interval Coloring of Complete Bipartite Graphs and Trees. Preprint of the Computing Centre of the Academy of Sciences of Armenia. (In Russian)

[7] Kamalian, R.R. (2010) On a Number of Colors in Cyclically Interval Edge Colorings of Trees. Research Report LiTHMAT-R-2010/09-SE, Linkoping University.

[8] Kamalian, R.R. (2012) On Cyclically-Interval Edge Colorings of Trees. Buletinul Academiei de Stiinte a Republicii Moldova Matematica, 68, 50-58.

[9] Bartholdi, J.J., Orlin, J.B. and Ratliff, H.D. (1980) Cyclic Scheduling via Integer Programs with Circular Ones. Operations Research, 28, 1074-1085.
http://dx.doi.org/10.1287/opre.28.5.1074

[10] Dauscha, W., Modrow, H.D. and Neumann, A. (1985) On Cyclic Sequence Type for Constructing Cyclic Schedules. Zeitschrift für Operations Research, 29, 1-30.
http://dx.doi.org/10.1007/bf01920492

[11] Werra, D., Mahadev, N.V.R. and Solot, P. (1989) Periodic Compact Scheduling. ORWP 89/18, Ecole Polytechnique Fédérale de Lausanne.

[12] Kamalian, R.R. (2007) On Cyclically Continues Edge Colorings of Simple Cycles. Proceedings of the Computer Science and Information Technologies Conference, Yerevan, 24-28 September 2007, 79-80. (In Russian)

[13] Kamalian, R.R. (2013) On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles. Open Journal of Discrete Mathematics, 3, 43-48.
http://dx.doi.org/10.4236/ojdm.2013.31009

[14] Petrosyan, P.A. and Mkhitaryan, S.T. (2014) Interval Cyclic Edge-Colorings of Graphs.
http://arxiv.org/abs/1411.0290v1

[15] West, D.B. (1996) Introduction to Graph Theory. Prentice Hall, Upper Saddle River.