Download PDF - Interval edge colorings of some products of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Interval edge colorings of some products of graphs

Authors 1, 2

Affiliations

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

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.

Keywords

ENG
edge coloring, interval coloring, regular graph, products of graphs

Bibliography

  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), doi: 10.1017/CBO9780511984068.
  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.
  5. M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94.
  6. C. Berge, Theorie des Graphes et ses Applications (Dunod, Paris, 1958).
  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.
  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.
  9. K. Giaro, The complexity of consecutive Δ-coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Combin. 47 (1997) 287-298.
  10. K. Giaro and M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr. Numer. 128 (1997) 143-149.
  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.
  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.
  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.
  14. H.M. Hansen, Scheduling with minimum waiting periods, Master's Thesis (Odense University, Odense, Denmark, 1992) (in Danish).
  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.
  16. D. Hanson, C.O.M. Loten and B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32.
  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.
  18. T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley Interscience Series in Discrete Mathematics and Optimization, 1995).
  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. R.R. Kamalian, Interval Edge Colorings of Graphs (Doctoral Thesis, Novosibirsk, 1990).
  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. R.R. Kamalian and P.A. Petrosyan, Interval colorings of some regular graphs, Math. Probl. Comp. Sci. 25 (2006) 53-56.
  23. R.R. Kamalian and P.A. Petrosyan, On interval colorings of complete k-partite graphs Knk, Math. Probl. Comp. Sci. 26 (2006) 28-32.
  24. A. Kotzig, 1-Factorizations of cartesian products of regular graphs, J. Graph Theory 3 (1979) 23-34, doi: 10.1002/jgt.3190030104.
  25. M. Kubale, ed., Graph Colorings (American Mathematical Society, 2004).
  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. B. Mohar and T. Pisanski, Edge-coloring of a family of regular graphs, Publ. Inst. Math. (Beograd) 33 (1983) 157-162.
  28. B. Mohar, On edge-colorability of products of graphs, Publ. Inst. Math. (Beograd) 36 (1984) 13-16.
  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. 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.
  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.
  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.
  33. G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967.
  34. A. Schwartz, The deficiency of a regular graph, Discrete Math. 306 (2006) 1947-1954, doi: 10.1016/j.disc.2006.03.059.
  35. S.V. Sevast'janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian).
  36. V.G. Vizing, The Cartesian product of graphs, Vych. Sis. 9 (1963) 30-43 (in Russian).
  37. D.B. West, Introduction to Graph Theory (Prentice-Hall, New Jersey, 1996).
  38. M.K. Zhou, Decomposition of some product graphs into 1-factors and Hamiltonian cycles, Ars Combin. 28 (1989) 258-268.
Discussiones Mathematicae Graph Theory
2011/31/2
Export to PBN, Opens in new tab
Pages:
357-373
Main language of publication
English
Received
2009-11-20
Accepted
2010-06-29
Published
2011

DOI: 10.7151/dmgt.1551

Exact and natural sciences