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 31(2) (2011) 357-373
DOI: https://doi.org/10.7151/dmgt.1551

INTERVAL EDGE COLORINGS OF SOME PRODUCTS OF GRAPHS

Petros A. Petrosyan

Institute for Informatics and Automation Problems
National Academy of Sciences, 0014, Armenia
Department of Informatics and Applied Mathematics
Yerevan State University, 0025, Armenia
e-mail: pet_petros@{ipia.sci.am, ysu.am, yahoo.com}

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[nK1] ∈ ℜ 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: edge coloring, interval coloring, regular graph, products of graphs.

2010 Mathematics Subject Classification: Primary: 05C15,
05C76; Secondary: 05C70.

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), 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.

Received 20 November 2009
Revised 29 June 2010
Accepted 2 July 2010

Close