Graph-coloring solver stress suite

Family 106: Hardness of coloring three-colorable graphs. First review, 8 October 2026.

Problem and potential new use

Constraint-solver teams can use structured difficult graph families to test coloring heuristics and claims about extra colors.

Applicability and commercial boundary

Hardness over three-colorable input graphs does not prove every real compatibility graph resists heuristic coloring. A polynomial reduction may create unrealistic instances.

Initial business decision

Research infrastructure. Buyer demand and profitability remain hypotheses. This first pass does not establish a validated commercial market.

Next verification action

Review the constructive reduction and compare any generated fixtures with established graph-coloring benchmarks.

Evidence scope

Catalog statement reviewed; inspect linked opportunity dossier for any deeper source review. This record alone does not establish full manuscript or proof verification.

Source revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. See source metadata for the exact manuscripts and available scope notes.