EDGE COLORING OF CACTUS GRAPHS WITH GIVEN SPECTRUMS
Abstract
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.
References
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.
Views:
310
Downloads:
200
Copyright (c) 2021 The author
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.
