Interval Edge-Colorings of Cartesian Products of Graphs I

• Autorzy: Petros A. Petrosyan , Hrant H. Khachatrian , Hovhannes G. Tananyan
• Języki publikacji: EN

Abstrakty

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 3
• Strony: 613-632

Daty

wydano

2013-07-01

online

2013-07-30

Twórcy

autor

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

autor

Hrant H. Khachatrian

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

autor

Hovhannes G. Tananyan

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

Bibliografia

• [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[Crossref]
• [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]
• [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[Crossref]
• [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.
• [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]
• [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).[WoS]
• [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[WoS][Crossref]
• [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]
• [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).

Identyfikatory

DOI

10.7151/dmgt.1693