Polynomial Algorithm for Finding Chromatic Sum for Unicyclic and Outerplanar Graphs

Abstract

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.