Discussiones Mathematicae Graph Theory 33(3) (2013)
613-632

doi: 10.7151/dmgt.1693

Petros A. Petrosyan
Department of Informatics and Applied Mathematics | Hrant H. Khachatrian
Department of Informatics and Applied Mathematics | Hovhannes G. Tananyan
Department of Applied Mathematics and Informatics |

**Keywords:** edge-coloring, interval coloring, grid, cylinder, torus, *n*-dimensional cube

**2010 Mathematics Subject Classification:** 05C15.

[1] | A.S. Asratian and R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25--34 (in Russian). |

[2] | A.S. Asratian and R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory (B) 62 (1994) 34--43, doi: 10.1006/jctb.1994.1053. |

[3] | A.S. Asratian, T.M.J. Denley and R. Häggkvist, Bipartite Graphs and their Applications (Cambridge University Press, Cambridge, 1998). |

[4] | M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77--94. |

[5] | M. Behzad and E.S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12 (1969) 157--166, doi: 10.4153/CMB-1969-015-9. |

[6] | Y. Feng and Q. Huang, Consecutive edge-coloring of the generalized , Discrete Appl. Math. θ-graph 155 (2007) 2321--2327, doi: 10.1016/j.dam.2007.06.010. |

[7] | K. Giaro and M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr. Numer. 128 (1997) 143--149. |

[8] | K. Giaro, M. Kubale and M. Małafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131--143, doi: 10.1016/S0012-365X(00)00437-4. |

[9] | K. Giaro and M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004) 95--103, doi: 10.1016/j.dam.2003.09.010. |

[10] | D. Hanson, C.O.M. Loten and B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23--32. |

[11] | R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011). |

[12] | T.R. Jensen, B. Toft, Graph Coloring Problems (Wiley Interscience Series in Discrete Mathematics and Optimization, 1995). |

[13] | R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. Acad. Sci. Armenian SSR, Erevan 1989 (in Russian). |

[14] | R.R. Kamalian, Interval edge colorings of graphs (Doctoral Thesis, Novosibirsk, 1990). |

[15] | R.R. Kamalian and A.N. Mirumian, Interval edge colorings of bipartite graphs of some class, Dokl. NAN RA 97 (1997) 3--5 (in Russian). |

[16] | R.R. Kamalian and P.A. Petrosyan, A note on upper bounds for the maximum span in interval edge-colorings of graphs, Discrete Math. 312 (2012) 1393--1399. |

[17] | R.R. Kamalian and P.A. Petrosyan, A note on interval edge-colorings of graphs, Mathematical Problems of Computer Science 36 (2012) 13--16. |

[18] | A. Khchoyan, Interval edge-colorings of subcubic graphs and multigraphs, Yerevan State University, BS Thesis {2010 30p. |

[19] | M. Kubale, Graph Colorings (American Mathematical Society, 2004). |

[20] | P.A. Petrosyan and G.H. Karapetyan, Lower bounds for the greatest possible number of colors in interval edge colorings of bipartite cylinders and bipartite tori, in: Proceedings of the CSIT Conference 2007 86--88. |

[21] | P.A. Petrosyan, Interval edge-colorings of complete graphs and , Discrete Math. n-dimensional cubes 310 (2010) 1580--1587, doi: 10.1016/j.disc.2010.02.001. |

[22] | P.A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph Theory 31 (2011) 357--373, doi: 10.7151/dmgt.1551. |

[23] | P.A. Petrosyan, H.H. Khachatrian, L.E. Yepremyan and H.G. Tananyan, Interval edge-colorings of graph products, in: Proceedings of the CSIT Conference 2011 89--92. |

[24] | S.V. Sevast'janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61--72 (in Russian). |

[25] | D.B. West, Introduction to Graph Theory (Prentice-Hall, New Jersey, 2001). |

Received 31 January 2012

Revised 5 March 2013

Accepted 5 March 2013