Interval edge colorings of some products of graphs

Petros A. Petrosyan

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 357-373
  • ISSN: 2083-5892

Abstract

top
An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs belongs to 𝔑. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ 𝔑, then G[nK₁] ∈ 𝔑 for any n ∈ ℕ. Furthermore, we show that if G,H ∈ 𝔑 and H is a regular graph, then strong and lexicographic products of graphs G,H belong to 𝔑. We also prove that tensor and strong tensor products of graphs G,H belong to 𝔑 if G ∈ 𝔑 and H is a regular graph.

How to cite

top

Petros A. Petrosyan. "Interval edge colorings of some products of graphs." Discussiones Mathematicae Graph Theory 31.2 (2011): 357-373. <http://eudml.org/doc/270969>.

@article{PetrosA2011,
abstract = {An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ \{1,2,...,t\} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs belongs to 𝔑. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ 𝔑, then G[nK₁] ∈ 𝔑 for any n ∈ ℕ. Furthermore, we show that if G,H ∈ 𝔑 and H is a regular graph, then strong and lexicographic products of graphs G,H belong to 𝔑. We also prove that tensor and strong tensor products of graphs G,H belong to 𝔑 if G ∈ 𝔑 and H is a regular graph.},
author = {Petros A. Petrosyan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; interval coloring; regular graph; products of graphs},
language = {eng},
number = {2},
pages = {357-373},
title = {Interval edge colorings of some products of graphs},
url = {http://eudml.org/doc/270969},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Petros A. Petrosyan
TI - Interval edge colorings of some products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 357
EP - 373
AB - An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs belongs to 𝔑. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ 𝔑, then G[nK₁] ∈ 𝔑 for any n ∈ ℕ. Furthermore, we show that if G,H ∈ 𝔑 and H is a regular graph, then strong and lexicographic products of graphs G,H belong to 𝔑. We also prove that tensor and strong tensor products of graphs G,H belong to 𝔑 if G ∈ 𝔑 and H is a regular graph.
LA - eng
KW - edge coloring; interval coloring; regular graph; products of graphs
UR - http://eudml.org/doc/270969
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. 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. Zbl0914.05049
  4. [4] A.S. Asratian, C.J. Casselgren, J. Vandenbussche and D.B. West, Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs, J. Graph Theory 61 (2009) 88-97, doi: 10.1002/jgt.20370. Zbl1198.05037
  5. [5] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94. Zbl1026.05036
  6. [6] C. Berge, Theorie des Graphes et ses Applications (Dunod, Paris, 1958). 
  7. [7] M. Bouchard, A. Hertz and G. Desaulniers, Lower bounds and a tabu search algorithm for the minimum deficiency problem, J. Comb. Optim. 17 (2009) 168-191, doi: 10.1007/s10878-007-9106-0. Zbl1180.90344
  8. [8] 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. Zbl1127.05037
  9. [9] K. Giaro, The complexity of consecutive Δ-coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Combin. 47 (1997) 287-298. Zbl0933.05050
  10. [10] K. Giaro and M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr. Numer. 128 (1997) 143-149. Zbl0903.05021
  11. [11] K. Giaro, M. Kubale and M. Maafiejski, On the deficiency of bipartite graphs, Discrete Appl. Math. 94 (1999) 193-203, doi: 10.1016/S0166-218X(99)00021-9. Zbl0933.05054
  12. [12] K. Giaro, M. Kubale and M. Maafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131-143, doi: 10.1016/S0012-365X(00)00437-4. Zbl1007.05045
  13. [13] 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. Zbl1056.05059
  14. [14] H.M. Hansen, Scheduling with minimum waiting periods, Master's Thesis (Odense University, Odense, Denmark, 1992) (in Danish). 
  15. [15] D. Hanson and C.O.M. Loten, A lower bound for interval coloring of bi-regular bipartite graphs, Bull. ICA 18 (1996) 69-74. Zbl0861.05024
  16. [16] 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
  17. [17] P.E. Himmelwright and J.E. Williamson, On 1-factorability and edge-colorability of Cartesian products of graphs, Elem. Der Math. 29 (1974) 66-67. Zbl0287.05117
  18. [18] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley Interscience Series in Discrete Mathematics and Optimization, 1995). 
  19. [19] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989 (in Russian). 
  20. [20] R.R. Kamalian, Interval Edge Colorings of Graphs (Doctoral Thesis, Novosibirsk, 1990). Zbl0805.05024
  21. [21] 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). 
  22. [22] R.R. Kamalian and P.A. Petrosyan, Interval colorings of some regular graphs, Math. Probl. Comp. Sci. 25 (2006) 53-56. 
  23. [23] R.R. Kamalian and P.A. Petrosyan, On interval colorings of complete k-partite graphs K n k , Math. Probl. Comp. Sci. 26 (2006) 28-32. 
  24. [24] A. Kotzig, 1-Factorizations of cartesian products of regular graphs, J. Graph Theory 3 (1979) 23-34, doi: 10.1002/jgt.3190030104. Zbl0395.05059
  25. [25] M. Kubale, ed., Graph Colorings (American Mathematical Society, 2004). 
  26. [26] E.S. Mahamoodian, On edge-colorability of Cartesian products of graphs, Canad. Math. Bull. 24 (1981) 107-108, doi: 10.4153/CMB-1981-017-9. 
  27. [27] B. Mohar and T. Pisanski, Edge-coloring of a family of regular graphs, Publ. Inst. Math. (Beograd) 33 (1983) 157-162. Zbl0517.05034
  28. [28] B. Mohar, On edge-colorability of products of graphs, Publ. Inst. Math. (Beograd) 36 (1984) 13-16. Zbl0569.05021
  29. [29] 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. 
  30. [30] 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. Zbl1210.05048
  31. [31] T. Pisanski, J. Shawe-Taylor and B. Mohar, 1-Factorization of the composition of regular graphs, Publ. Inst. Math. (Beograd) 33 (1983) 193-196. Zbl0517.05052
  32. [32] A.V. Pyatkin, Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs, J. Graph Theory 47 (2004) 122-128, doi: 10.1002/jgt.20021. Zbl1055.05064
  33. [33] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967. Zbl0093.37603
  34. [34] A. Schwartz, The deficiency of a regular graph, Discrete Math. 306 (2006) 1947-1954, doi: 10.1016/j.disc.2006.03.059. Zbl1099.05037
  35. [35] S.V. Sevast'janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian). 
  36. [36] V.G. Vizing, The Cartesian product of graphs, Vych. Sis. 9 (1963) 30-43 (in Russian). 
  37. [37] D.B. West, Introduction to Graph Theory (Prentice-Hall, New Jersey, 1996). Zbl0845.05001
  38. [38] M.K. Zhou, Decomposition of some product graphs into 1-factors and Hamiltonian cycles, Ars Combin. 28 (1989) 258-268. Zbl0766.05069

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.