Geodesic
Interval Edge-Colorings of Cartesian Products of Graphs I
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 613-632.

Voir la notice de l'article provenant de la source Library of Science

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 □ P_m) ≥ W(G) + W(P_m) + (m − 1)r (m ∈ℕ) and W(G □ C_2n) ≥ W(G) +W(C_2n) + 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 ∈𝔑 and w(G □ H) leq 6. Finally, we confirm the first author’s conjecture on the n-dimensional cube Q_n and show that Q_n has an interval t-coloring if and only if n ≤ t ≤n(n+1)/2. 
@article{DMGT_2013_33_3_a10,
     author = {Petrosyan, Petros A. and Khachatrian, Hrant H. and Tananyan, Hovhannes G.},
     title = {Interval {Edge-Colorings} of {Cartesian} {Products} of {Graphs} {I}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {613--632},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a10/}
}
TY  - JOUR
AU  - Petrosyan, Petros A.
AU  - Khachatrian, Hrant H.
AU  - Tananyan, Hovhannes G.
TI  - Interval Edge-Colorings of Cartesian Products of Graphs I
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 613
EP  - 632
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a10/
LA  - en
ID  - DMGT_2013_33_3_a10
ER  - 
%0 Journal Article
%A Petrosyan, Petros A.
%A Khachatrian, Hrant H.
%A Tananyan, Hovhannes G.
%T Interval Edge-Colorings of Cartesian Products of Graphs I
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 613-632
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a10/
%G en
%F DMGT_2013_33_3_a10
Petrosyan, Petros A.; Khachatrian, Hrant H.; Tananyan, Hovhannes G. Interval Edge-Colorings of Cartesian Products of Graphs I. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 613-632. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a10/

[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). doi:10.1017/CBO9780511984068

[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 θ-graph, Discrete Appl. Math. 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 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

[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

[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 n-dimensional cubes, Discrete Math. 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).