Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs
2026-06-30 • Computational Complexity
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study the Chromatic Sum problem, which asks if a graph's vertices can be colored with numbers adding up to at most a given value. They analyze how hard this problem is on different types of graphs defined by forbidden patterns. By creating new proofs, they fully classify its complexity on graphs excluding certain minors or subgraphs and extend these results to graphs excluding certain induced subgraphs. They also show the problem is NP-complete on graphs with low clique-width, improving the understanding of where the problem is computationally easy or hard.
Chromatic SumGraph ColoringNP-completenessGraph MinorsTopological MinorsInduced SubgraphsClique-widthPlanar GraphsSubcubic Graphs
Authors
Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen
Abstract
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 subcubic graphs. Next, we consider other containment relations. We formalise a novel framework of problems that are NP-complete for planar graphs as well as for graphs of bounded independence number. For every problem in this framework, we obtain an almost complete complexity classification on $H$-induced-minor-free graphs, $H$-induced-topological-minor-free graphs, and $H$-free graphs for every graph $H$. We show that Chromatic Sum belongs to this framework, as do several other problems. We also define a more fine-grained framework for the induced subgraph relation. We apply this to obtain a complete complexity classification for Chromatic Sum on $H$-free graphs, as well as for several other problems. We justify the choice of this framework by proving that Chromatic Sum is NP-complete for graphs of clique-width at most $3$. This result complements a known polynomial-time result for graphs of clique-width at most $2$.