Graph Classes with Recursive Chromatic-Polynomial Algorithms

Definitions and mathematical statement

Characterization problem. Characterize, by simple structural properties or forbidden minors, the graphs whose chromatic polynomials can be computed efficiently by the report's recursion involving passage to complements. The intended family includes bounded-treewidth graphs and graphs with bounded-treewidth complements. For a finite simple graph $G$, its chromatic polynomial $P_G(q)$ counts proper colorings with $q$ labeled colors at nonnegative integers $q$; its complement $\overline G$ has the same vertices and exactly the missing edges between distinct vertices. Treewidth is the minimum of the largest bag size minus one over tree decompositions.

A meaningful bounded-width algorithmic formulation fixes a uniform width bound $k$ and asks for a structural description of the specified recursive class $\mathcal C_k$, at least containing every $G$ with $\operatorname{tw}(G)\le k$ or $\operatorname{tw}(\overline G)\le k$. It should also specify the running-time dependence on graph size, $k$, and the output convention. Allowing the width bound to depend arbitrarily on each individual finite graph would impose no restriction. The report's actual recursive reduction, auxiliary operations, stopping rule, and admissible decomposition are not supplied; complementation alone is an involution and does not define the larger recursively generated class. No guessed closure rule is inserted.

Forbidden-minor qualification. If ordinary graph minors are intended, a proper class containing all graphs with treewidth-zero complements cannot be minor closed: it contains every complete graph $K_n$, and every finite simple graph is a minor of a sufficiently large complete graph. Thus a characterization of such a proper class solely by exclusion of ordinary minors is impossible under the literal inclusion requirement. The source's alternative request for simple structural properties is retained; a different relation, such as an induced or complement-based obstruction, would need an explicit source definition rather than silently replacing minor. This observation diagnoses a formulation issue, not a characterization of the missing recursive class.

The supplied triage checked 2026-08-21 labels the problem open and says the report describes the alternating treewidth/complementation class but no simple structural or forbidden-minor characterization was found. The class description is not reproduced in this record. The dated assessment therefore does not remove the missing recursion or the ordinary-minor obstruction and requires independent verification.

Short English statement

Describe the particular complement-recursive class supporting efficient chromatic-polynomial computation, with a fixed width parameter. Its recursion is missing. A proper class containing all complete graphs cannot be characterized by ordinary forbidden minors, so that proposed route needs qualification.

Sources

• Local UnsolvedMath registry, permanent ID 30000415, code catalogue entry; Graph Classes with Recursive Chromatic-Polynomial Algorithms, Oberwolfach Reports Open Problems.
• Algorithmic Graph Theory (2006), Oberwolfach Reports, DOI 10.4171/owr/2006/07, pp. 379--460. https://doi.org/10.4171/owr/2006/07. Proposed year 2006; no proposer named.
• Supplied literature label original OWR report: https://doi.org/10.4171/owr/2006/07. No separate algorithm specification or structural theorem is supplied.
• Literature triage checked 2026-08-21, status open; record updated 2026-09-16. The corrected_verified field describes wording changes preserving both comparison families and both proposed characterization routes. Verify dated claims independently.