The chromatic sum of \(G\), denoted by \(\sum(G)\), is the minimum sum of vertex colors, taken over all proper colorings of \(G\) using natural numbers. In general, finding \(\sum(G)\) is NP-complete. This paper presents polynomial-time algorithms for finding the chromatic sum for unicyclic graphs and for outerplanar graphs.
Citation
Ewa M.Kubicka. Polynomial Algorithm for Finding Chromatic Sum for Unicyclic and Outerplanar Graphs[J], Ars Combinatoria, Volume 076. 193-201. .