Back
 OJDM  Vol.6 No.3 , July 2016
Note on 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 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”.
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.

 
 
Top