# Interval Edge-Colorings of Cartesian Products of Graphs I

Petros A. Petrosyan; Hrant H. Khachatrian; Hovhannes G. Tananyan

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 3, page 613-632
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPetros A. Petrosyan, Hrant H. Khachatrian, and Hovhannes G. Tananyan. "Interval Edge-Colorings of Cartesian Products of Graphs I." Discussiones Mathematicae Graph Theory 33.3 (2013): 613-632. <http://eudml.org/doc/267853>.

@article{PetrosA2013,

abstract = {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 ≤ [...]},

author = {Petros A. Petrosyan, Hrant H. Khachatrian, Hovhannes G. Tananyan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge-coloring; interval coloring; grid; cylinder; torus; -dimensional cube},

language = {eng},

number = {3},

pages = {613-632},

title = {Interval Edge-Colorings of Cartesian Products of Graphs I},

url = {http://eudml.org/doc/267853},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Petros A. Petrosyan

AU - Hrant H. Khachatrian

AU - Hovhannes G. Tananyan

TI - Interval Edge-Colorings of Cartesian Products of Graphs I

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 3

SP - 613

EP - 632

AB - 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 ≤ [...]

LA - eng

KW - edge-coloring; interval coloring; grid; cylinder; torus; -dimensional cube

UR - http://eudml.org/doc/267853

ER -

## References

top- [1] A.S. Asratian and R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25-34 (in Russian). Zbl0805.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] Zbl0805.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] Zbl0914.05049
- [4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94. Zbl1026.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] Zbl0177.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. Zbl0903.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] Zbl1056.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. Zbl0963.05049
- [11] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011). Zbl1283.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] Zbl0805.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. Zbl1237.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. Zbl1237.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] Zbl1210.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] Zbl1234.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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.