Cost Edge-Coloring of a Cactus


Let C be a set of colors, and let  be an integer cost assigned to a color c in C. An edge-coloring of a graph  is assigning a color in C to each edge  so that any two edges having end-vertex in common have different colors. The cost  of an edge-coloring f of G is the sum of costs  of colors  assigned to all edges e in G. An edge-coloring f of G is optimal if  is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge-   coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.

Share and Cite:

Ye, Z. , Li, Y. , Lu, H. and Zhou, X. (2015) Cost Edge-Coloring of a Cactus. World Journal of Engineering and Technology, 3, 119-134. doi: 10.4236/wjet.2015.33C018.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] West, D.B. (2000) Introduction to Graph Theory. 2nd Edition, Prentice Hall, New Jersey.
[2] Hajiabolhassan, H., Mehrabadi, M.L. and Tusserkani, R. (2000) Minimal Coloring and Strength of Graphs. Discrete Mathematics, 215, 265-270.
[3] Mitchem, J., Morriss, P. and Schmeichel, E. (1997) On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discussiones Mathematicae Graph Theory, 17, 229-241.
[4] Giaro, K. and Kubale, M. (2000) Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Information Process- ing Letters, 75, 65-69.
[5] Zhou, X. and Nishizeki, T. (2004) Algorithm for the Cost Edge-Coloring of Trees. J. Combinatorial Optimization, 8, 97-108.
[6] Coffman, E.G., Garey, M.R., Johnson, D.S. and LaPaugh, A.S. (1985) Scheduling File Transfers. SIAM J. Computing, 14, 744-780.
[7] Krawczyk, H. and Kubale, M. (1985) An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems. IEEE Trans. Computers, 34, 869-872.
[8] Marx, D. (2009) Complexity Results for Minimum Sum Edge Co-loring. Discrete Applied Mathematics, 157, 1034- 1045.
[9] Goldberg, A.V. and Tarjan, R.E. (1987) Solving Minimum Cost Flow Problems by Successive Approximation. Proc. 19th ACM Symposium on the Theory of Computing, 7-18.
[10] Goldberg, A.V. and Tar-jan, R.E. (1989) Finding Minimum-Cost Circulations by Canceling Negative Cycles. J. ACM, 36, 873-886.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.