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

Abstract

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

How to cite

top

Petros 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. [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. [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. [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. [4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94. Zbl1026.05036
  5. [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. [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. [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. [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. [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. [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. [11] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011). Zbl1283.05001
  12. [12] T.R. Jensen, B. Toft, Graph Coloring Problems (Wiley Interscience Series in Discrete Mathematics and Optimization, 1995). 
  13. [13] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint , Comp. Cen. Acad. Sci. Armenian SSR, Erevan (1989) (in Russian). 
  14. [14] R.R. Kamalian, Interval edge colorings of graphs (Doctoral Thesis, Novosibirsk, 1990).[WoS] Zbl0805.05024
  15. [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. [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. [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. [18] A. Khchoyan, Interval edge-colorings of subcubic graphs and multigraphs, Yerevan State University, BS Thesis (2010) 30p. 
  19. [19] M. Kubale, Graph Colorings (American Mathematical Society, 2004). 
  20. [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. [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. [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. [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. [24] S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian). 
  25. [25] D.B. West, Introduction to Graph Theory (Prentice-Hall, New Jersey, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.