# Interval edge colorings of some products of graphs

Discussiones Mathematicae Graph Theory (2011)

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

## Access Full Article

top## Abstract

top## How to cite

topPetros 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] 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] 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] 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] 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] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94. Zbl1026.05036
- [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. Zbl1180.90344
- [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] 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] 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] 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] 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] 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] 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. Zbl0861.05024
- [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] 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] 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). Zbl0805.05024
- [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 ${K}_{n}^{k}$, 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. Zbl0395.05059
- [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. Zbl0517.05034
- [28] B. Mohar, On edge-colorability of products of graphs, Publ. Inst. Math. (Beograd) 36 (1984) 13-16. Zbl0569.05021
- [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. Zbl1210.05048
- [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] 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] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967. Zbl0093.37603
- [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] 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). Zbl0845.05001
- [38] M.K. Zhou, Decomposition of some product graphs into 1-factors and Hamiltonian cycles, Ars Combin. 28 (1989) 258-268. Zbl0766.05069