INTERVAL EDGE COLORING OF TREES WITH STRICT RESTRICTIONS ON THE SPECTRUMS
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:
376
Downloads:
267
Copyright (c) 2021 Albert Khachik Sahakyan
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles are published in open-access and licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Hence, authors retain copyright to the content of the articles.
CC BY 4.0 License allows content to be copied, adapted, displayed, distributed, re-published or otherwise re-used for any purpose including for adaptation and commercial use provided the content is attributed.
