INTERVAL EDGE COLORING OF TREES WITH STRICT RESTRICTIONS ON THE SPECTRUMS

  • Albert Khachik Sahakyan Chair of Discrete Mathematics and Theoretical Informatics, Faculty of Informatics and Applied Mathematics, Yerevan State University, Armenia
Keywords: trees, interval t-coloring, interval edge coloring, restrictions on spectrums, dynamic programming

Abstract

An edge-coloring of a graph G with consecutive integers C1 ,..., Ct is called an interval t-coloring if all the colors are used, 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 it has an interval t-coloring for some positive integer t. For an edge coloring a and a vertex v the set of all the colors of the incident edges of v is called the spectrum of that vertex in a 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 a such that for every vertex v, Sa(v)=S(v). We provide an O(N) algorithm that finds such an edge-coloring for trees that satisfies all the restrictions. If it is impossible to have an edge-coloring that satisfies the restrictions of the spectrums the algorithm will tell that too.

References

R.R. Kamalian "Interval colorings of complete bipartite graphs and trees", Preprint of the Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989

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

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

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

Kuhn, H. (1955). The Hungarian method for the assignment problem. Naval research logistics quarterly, 2, 83-97. doi: 10.1002/nav.3800020109

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

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

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

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

Views:

259

Downloads:

191

Published
2021-06-15
Citations
How to Cite
Albert Khachik Sahakyan. (2021). INTERVAL EDGE COLORING OF TREES WITH STRICT RESTRICTIONS ON THE SPECTRUMS. Science Review, (3(38). https://doi.org/10.31435/rsglobal_sr/30072021/7592
Section
Computer Science