• Albert Khachik Sahakyan Chair of Discrete Mathematics and Theoretical Informatics, Faculty of Informatics and Applied Mathematics, Yerevan State University, Armenia
Keywords: cactus graphs, block-cut tree, edge coloring, restrictions on spectrums, dynamic programming


An edge-coloring of a graph G is a coloring of the graph edges with integers such that the colors of the edges incident to any vertex of G are distinct. For an edge coloring α and a vertex v the set of all the colors of the incident edges of v is called the spectrum of that vertex in α and is denoted by Sa(V). We consider the case where the spectrum for each vertex V is provided S(V), and the problem is to find an edge-coloring α such that for every vertex V, Sa(V) = S(V). We provide an O(N2) algorithm that inds such an edge-coloring for cactus graphs that satisfies all the restrictions. If it is impossible to have an edge-coloring hat satisfiesthe restrictions of the spectrums the algorithm will tell that too.


West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996.

Caro Y., Schönheim J. Generalized 1-factorization of trees. Discrete Mathematics, 33, (1981) 319-321. https://doi.org/10.1016/0012-365X(81)90275-2

Kubale M. Interval vertex-coloring of a graph with forbidden colors. Discret. Math., 74, (1989) 125-136.

Kamalian R.R. Interval edge-colorings of graphs. Doctoral Thesis. Novosibirsk, 1990.

Even S., Itai A., Shamir A. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM J. Comput., 5, (1976) 691-703.

Asratian A.S. Investigation of Some Mathematical Model of Scheduling Theory. Doctoral dissertation. Moscow University, 1980

Asratian A.S., Kamalian R.R. Interval colorings of edges of a multigraph.Appl. Math.5(1987) 25–34. (in Russian).

Giaro, K., Rubale, M., & Malafiejski, M. Compact Scheduling in Open Shop with Zero-One Time Operations. INFOR: Information Systems and Operational Research, 37(1), (1999) 37–47. https://doi.org/10.1080/03155986.1999.11732367

Harary F. Graph Theory. Addison-Wesley Publishing Company, Boston, 1969.

How to Cite
Albert Khachik Sahakyan. (2021). EDGE COLORING OF CACTUS GRAPHS WITH GIVEN SPECTRUMS. International Academy Journal Web of Scholar, (2(52). https://doi.org/10.31435/rsglobal_wos/30062021/7617