Pith. sign in

REVIEW 1 major objections 2 minor 15 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

Three frameworks classify the complexity of Chromatic Sum on all HH-minor-free, HH-topological-minor-free, and finite HH-subgraph-free graph classes.

2026-07-02 18:06 UTC pith:HPWV3W63

load-bearing objection Extends three frameworks to Chromatic Sum and adds one targeted NP-completeness result on planar subdivisions to obtain full dichotomies on the main forbidden-structure classes. the 1 major comments →

arxiv 2607.00263 v1 pith:HPWV3W63 submitted 2026-06-30 math.CO cs.CCcs.DMcs.DS

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

Cl\'ement Dallard , Dani\"el Paulusma , Erik Jan van Leeuwen This is my paper
classification math.CO cs.CCcs.DMcs.DS
keywords Chromatic Sumgraph colouringcomputational complexityforbidden graphsminor-free graphsNP-completenessclique-width
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that three existing frameworks completely determine whether Chromatic Sum is polynomial-time solvable or NP-complete on every graph class defined by forbidding a set of minors, topological minors, or subgraphs. To reach this classification the authors first establish a new NP-completeness result for Chromatic Sum on subdivisions of planar subcubic graphs. They then place Chromatic Sum inside two additional frameworks, one that yields almost-complete classifications on induced-minor-free and induced-topological-minor-free graphs and one that yields a complete classification on ordinary H-free graphs. The work also proves that Chromatic Sum remains NP-complete on graphs of clique-width at most 3, confirming that the second framework is the right granularity for the induced-subgraph relation.

Core claim

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. This classification rests on a new NP-completeness proof for Chromatic Sum on certain subdivisions of planar subcubic graphs. Chromatic Sum also belongs to a framework of problems that are NP-complete both on planar graphs and on graphs of bounded independence number; membership in this framework produces 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. A finer framework

What carries the argument

The three known complexity-classification frameworks for forbidden-minor and forbidden-subgraph classes, powered by a new NP-completeness reduction on subdivisions of planar subcubic graphs.

Load-bearing premise

The new NP-completeness reduction for Chromatic Sum on subdivisions of planar subcubic graphs is correct and transfers to the relevant forbidden-structure classes.

What would settle it

A polynomial-time algorithm that solves Chromatic Sum on every subdivision of a planar subcubic graph would falsify the hardness side of the claimed classifications.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Chromatic Sum is polynomial-time solvable or NP-complete on every HH-minor-free class, every HH-topological-minor-free class, and every finite HH-subgraph-free class.
  • Chromatic Sum belongs to the framework of problems NP-complete on both planar graphs and bounded-independence-number graphs.
  • Chromatic Sum is NP-complete on graphs of clique-width at most 3.
  • Several other problems in the same frameworks inherit the same almost-complete and complete classifications on the listed graph classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same frameworks may apply to other sum or cost variants of coloring problems not examined in the paper.
  • The clique-width-3 hardness result suggests that any dynamic-programming approach on clique-width decompositions cannot be polynomial for Chromatic Sum once width exceeds 2.
  • The reduction technique on planar subdivisions could be reused to classify additional problems inside the same frameworks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. The paper claims 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. This classification is obtained via a new NP-completeness result for Chromatic Sum on subdivisions of planar subcubic graphs. The manuscript further introduces a framework for problems NP-complete both on planar graphs and on graphs of bounded independence number, yielding almost-complete classifications on H-induced-minor-free, H-induced-topological-minor-free, and H-free graphs; a finer framework for the induced-subgraph relation then gives complete classifications on H-free graphs. Chromatic Sum is shown to belong to both frameworks, with membership in the latter justified by an NP-completeness proof for graphs of clique-width at most 3 (complementing the known polynomial-time case for clique-width 2).

Significance. If the new reduction is correct and the framework applications are valid, the manuscript supplies a systematic, largely complete complexity map for Chromatic Sum (and several other problems) across the principal hereditary classes defined by forbidden minors, topological minors, subgraphs, and induced subgraphs. Explicit credit is due for the reuse of three existing frameworks, the provision of a single reduction that populates multiple hardness sides, and the clique-width-3 hardness result that anchors the fine-grained dichotomy.

major comments (1)
  1. [new NP-completeness result] The new NP-completeness reduction for Chromatic Sum on subdivisions of planar subcubic graphs (the section titled 'new NP-completeness result') is load-bearing for the hardness direction of all three claimed dichotomies. The manuscript must verify that the constructed instances satisfy the precise structural conditions that trigger the known hardness cases inside each of the three frameworks.
minor comments (2)
  1. The abstract packs three distinct classification statements into a single sentence; separating them would improve readability.
  2. Notation for the forbidden sets (HH versus H) is introduced without an explicit global convention; a short paragraph in the introduction would prevent confusion when the same symbol is reused for different relations.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The positive assessment of the paper's contributions and the significance of the new reduction and frameworks is appreciated. We respond to the single major comment below.

read point-by-point responses

  1. Referee: [new NP-completeness result] The new NP-completeness reduction for Chromatic Sum on subdivisions of planar subcubic graphs (the section titled 'new NP-completeness result') is load-bearing for the hardness direction of all three claimed dichotomies. The manuscript must verify that the constructed instances satisfy the precise structural conditions that trigger the known hardness cases inside each of the three frameworks.

    Authors: We agree that the reduction is central and that explicit verification of the structural conditions improves clarity. The graphs produced by the reduction in Section 3 are subdivisions of planar subcubic graphs; this class is chosen precisely because it meets the input requirements of the hardness statements in each of the three reused frameworks (the minor-free framework of [reference], the topological-minor-free framework of [reference], and the finite subgraph-free framework of [reference]). In the revised manuscript we will add a short paragraph immediately following the reduction that (i) recalls the exact structural hypothesis of each framework's hardness case and (ii) confirms that every constructed instance satisfies it. This is a presentational clarification; the correctness of the reduction itself is unaffected. revision: yes

Circularity Check

0 steps flagged

No circularity: classifications rest on independent known frameworks and a new explicit reduction

full rationale

The paper applies three known external frameworks to classify Chromatic Sum complexity on the relevant forbidden-structure classes and supports the hardness direction via a newly proved NP-completeness reduction on subdivisions of planar subcubic graphs. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear; the derivation chain consists of explicit reductions and applications of independently stated prior results. The central claims therefore remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic assumptions and the validity of three previously published meta-frameworks; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Graphs are finite, undirected, and simple
    Implicit throughout all complexity statements on forbidden subgraphs and minors.

pith-pipeline@v0.9.1-grok · 5853 in / 1136 out tokens · 33805 ms · 2026-07-02T18:06:25.456692+00:00 · methodology

0 comments
read the original 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$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 2 canonical work pages

  1. [1]

    Optimal b-colourings and fall colourings inH-free graphs.Proc

    1 Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniel Paulusma. Optimal b-colourings and fall colourings inH-free graphs.Proc. WG 2026, LIPIcs, 326:12:1–12:16,

    2026

  2. [2]

    Bodlaender, Danny Hermelin, and Erik Jan van Leeuwen

    9 Hans L. Bodlaender, Danny Hermelin, and Erik Jan van Leeuwen. Concurrency constrained scheduling with tree-like constraints. InProc. WG 2025, volume 16124 ofLNCS, pages 105–120. Springer,

    2025

  3. [3]

    Colouring graphs without a subdivided H-graph: A full complexity classification.Proc

    17 Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, and Daniël Paulusma. Colouring graphs without a subdivided H-graph: A full complexity classification.Proc. WG 2026, LIPIcs, to appear,

    2026

  4. [4]

    Maximum Weight Independent Set in graphs with no long claws in quasi-polynomial time.Proc

    24 Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Maximum Weight Independent Set in graphs with no long claws in quasi-polynomial time.Proc. STOC 2024, pages 683–691,

    2024

  5. [5]

    A27/26- approximation algorithm for the Chromatic Sum Coloring of bipartite graphs.Proc

    26 Krzysztof Giaro, Robert Janczewski, Marek Kubale, and Michał Małlafiejski. A27/26- approximation algorithm for the Chromatic Sum Coloring of bipartite graphs.Proc. APPROX 2002, Lecture Notes in Computer Science, pages 135–145,

    2002

  6. [6]

    The Optimum Cost Chromatic Partition problem

    36 Klaus Jansen. The Optimum Cost Chromatic Partition problem. InProc. CIAC 1997, volume 1203 ofLNCS, pages 25–36,

    1997

  7. [7]

    Complexity framework for forbidden subgraphs III: When problems are polynomial on subcubic graphs.Proc

    38 Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity framework for forbidden subgraphs III: When problems are polynomial on subcubic graphs.Proc. MFCS 2023, LIPIcs, 272:57:1–57:15,

    2023

  8. [8]

    Contracting to a longest path inH-free graphs.Proc

    39 Walter Kern and Daniël Paulusma. Contracting to a longest path inH-free graphs.Proc. ISAAC 2020, LIPIcs, 181:22:1–22:18,

    2020

  9. [9]

    Woeginger

    42 Daniel Král’, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs.Proc. WG 2001, LNCS, 2204:254–262,

    2001

  10. [10]

    Thechromaticsumofagraph: historyandrecentdevelopments.International Journal of Mathematics and Mathematical Sciences, 2004:1563–1573,

    43 EwaM.Kubicka. Thechromaticsumofagraph: historyandrecentdevelopments.International Journal of Mathematics and Mathematical Sciences, 2004:1563–1573,

    2004

  11. [11]

    Kubicka and Allen J

    44 Ewa M. Kubicka and Allen J. Schwenk. An introduction to chromatic sums. InProc. ACM CSC 1989, pages 39–45,

    1989

  12. [12]

    Complexity framework for forbidden subgraphs II: Edge subdivision and the “H”-graphs.Proc

    47 Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen. Complexity framework for forbidden subgraphs II: Edge subdivision and the “H”-graphs.Proc. ISAAC 2024, LIPIcs, 322:47:1–47:18,

    2024

  13. [13]

    Finding minimum matching cuts in H-free graphs and graphs of bounded radius and diameter.CoRR, abs/2502.18942,

    49 Felicia Lucke, Joseph Marchand, and Jannik Olbrich. Finding minimum matching cuts in H-free graphs and graphs of bounded radius and diameter.CoRR, abs/2502.18942,

    work page arXiv

  14. [14]

    51 Michal Malafiejski, Krzysztof Giaro, Robert Janczewski, and Marek Kubale

    URL: https: //doi.org/10.1016/S1571-0653(05)80080-0. 51 Michal Malafiejski, Krzysztof Giaro, Robert Janczewski, and Marek Kubale. Sum coloring of bipartite graphs with bounded degree.Algorithmica, 40:235–244,

    work page doi:10.1016/s1571-0653(05)80080-0

  15. [15]

    Routing with minimum wire length in the dogleg-free manhattan model is NP-complete.SIAM Journal on Computing, 29:274–287, 1999

    64 Tibor Szkaliczki. Routing with minimum wire length in the dogleg-free manhattan model is NP-complete.SIAM Journal on Computing, 29:274–287, 1999

    1999