A proper edge-coloring of a graph G with colors 1, . . . , t is an interval t-coloring if all colors are used and the colors of edges incident to each vertex of G form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. Let [...] be the set of all interval colorable graphs. For a graph G ∈ [...] , the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively. In this paper we first show that if G is an r-regular graph and G ∈ [...] , then W(G⃞Pm) ≥ W(G) + W(Pm) + (m − 1)r (m ∈ N) and W(G⃞C2n) ≥ W(G) +W(C2n) + nr (n ≥ 2). Next, we investigate interval edge-colorings of grids, cylinders and tori. In particular, we prove that if G⃞H is planar and both factors have at least 3 vertices, then G⃞H [...] N and w(G⃞H) ≤ 6. Finally, we confirm the first author’s conjecture on the n-dimensional cube Qn and show that Qn has an interval t-coloring if and only if n ≤ t ≤ [...]
@article{bwmeta1.element.doi-10_7151_dmgt_1693,
author = {Petros A. Petrosyan and Hrant H. Khachatrian and Hovhannes G. Tananyan},
title = {Interval Edge-Colorings of Cartesian Products of Graphs I},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {613-632},
zbl = {1275.05023},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1693}
}
Petros A. Petrosyan; Hrant H. Khachatrian; Hovhannes G. Tananyan. Interval Edge-Colorings of Cartesian Products of Graphs I. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 613-632. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1693/
[1] A.S. Asratian and R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25-34 (in Russian). | Zbl 0805.05024
[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[Crossref] | Zbl 0805.05024
[3] A.S. Asratian, T.M.J. Denley and R. Häggkvist, Bipartite Graphs and their Applications (Cambridge University Press, Cambridge, 1998). doi:10.1017/CBO9780511984068[Crossref] | Zbl 0914.05049
[4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94. | Zbl 1026.05036
[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[Crossref] | Zbl 0177.52402
[6] Y. Feng and Q. Huang, Consecutive edge-coloring of the generalized θ-graph, Discrete Appl. Math. 155 (2007) 2321-2327. doi:10.1016/j.dam.2007.06.010[WoS][Crossref]
[7] K. Giaro and M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr. Numer. 128 (1997) 143-149. | Zbl 0903.05021
[8] K. Giaro, M. Kubale andM.Ma lafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131-143. doi:10.1016/S0012-365X(00)00437-4 [Crossref]
[9] K. Giaro and M. Kubale, Compact scheduling of zero-one time operations in multistage systems, Discrete Appl. Math. 145 (2004) 95-103. doi:10.1016/j.dam.2003.09.010[Crossref] | Zbl 1056.05059
[10] D. Hanson, C.O.M. Loten and B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32. | Zbl 0963.05049
[11] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011). | Zbl 1283.05001
[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).[WoS] | Zbl 0805.05024
[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. | Zbl 1237.05079
[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. | Zbl 1237.05079
[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 n-dimensional cubes, Discrete Math. 310 (2010) 1580-1587. doi:10.1016/j.disc.2010.02.001[WoS][Crossref] | Zbl 1210.05048
[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[Crossref] | Zbl 1234.05103
[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).