Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen

The Chromatic Sum problem asks, given a graph $G$ and an integer $k$, whether $G$ admits a colouring $c$ with sum ${\sum }_{v\in V}c(v)\le k$. We study the complexity of Chromatic S…