Id: arxiv/2607.00263 Url: https://arxiv.org/abs/2607.00263 Tags: math.CO, cs.CC, cs.DM, cs.DS Score: 0 Title: Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs Domain: math.CO Source: arxiv Authors: Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-30 Page: https://delphi.science/r/arxiv/2607.00263 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) \leq k$. We study the complexity of Chromatic Sum on graph classes defined by some set of forbidden graphs. First, we show that three known frameworks fully classify the complexity of Chromatic Sum on $HH$-minor-free graphs and $HH$-topological-minor-free graphs for any set of graphs $HH$, and on $HH$-subgraph-free graphs for any finite set of graphs $HH$. To show this, we prove a new NP-completeness result for Chromatic Sum on certain subdivisions of planar…