DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(3) (2013) 613-632
DOI: https://doi.org/10.7151/dmgt.1693

Interval edge-colorings of Cartesian products of graphs I

Petros A. Petrosyan

Department of Informatics and Applied Mathematics
Yerevan State University, 0025, Armenia
Institute for Informatics and Automation Problems
National Academy of Sciences, 0014, Armenia

Hrant H. Khachatrian

Department of Informatics and Applied Mathematics
Yerevan State University, 0025, Armenia

Hovhannes G. Tananyan

Department of Applied Mathematics and Informatics
Russian-Armenian State University, 0051, Armenia

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 ∈ ℕ) 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 ∈ ℕ 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 ≤ n(n+1)/2.

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

2010 Mathematics Subject Classification: 05C15.

References

[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 θ-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 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 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).

Received 31 January 2012
Revised 5 March 2013
Accepted 5 March 2013

Close