Abstract
The Chromatic Sum problem asks whether a graph $G$ admits a colouring $c$ such that for all $v \text{ in } V, \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.
Key Findings
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 demonstrate 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 NP-complete problems for planar graphs and graphs of bounded independence number. For every problem in this framework, we achieve an almost complete complexity classification on $H$-induced-minor-free graphs, $H$-induced-topological-minor-free graphs, and $H$-free graphs for any 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 framework to obtain a complete complexity classification for Chromatic Sum on $H$-free graphs, as well as for several other problems. We justify this framework choice by proving that Chromatic Sum is NP-complete for graphs with clique-width at most $3$, complementing a known polynomial-time result for graphs with clique-width at most $2$.
Blogger's Review: This paper provides a fresh perspective on the complexity of the Chromatic Sum problem across various graph classes. The in-depth analysis of NP-completeness showcases how structural properties of graphs influence computational complexity, which is significant both theoretically and practically. I look forward to more studies like this that further unveil the complexities within graph theory.