Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 106: claimed hardness of coloring three-colorable graphs
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This is a documentary record of the pinned publisher's claim, not an independent verification of its proof.
The question in plain language
A graph coloring assigns colors to vertices so that endpoints of every edge receive different colors. A three-colorable graph has some valid coloring with just three colors, but finding it may be difficult. The approximate-coloring question asks whether a polynomial-time algorithm can use a larger, but fixed, number of colors on every graph promised to be three-colorable.
Family 106 concerns a claimed hardness theorem at every fixed number of colors, derived from a stronger gap involving independent sets.
A small example
A triangle needs three colors. It is trivially possible to give each vertex its own distinct color, but a graph with millions of vertices cannot be colored with a fixed number of colors by this strategy. An independent set is a collection of vertices with no edges among them; any single color class in a proper coloring is an independent set.
If a graph on \(n\) vertices is properly colored with \(c\) colors, at least one color class contains at least \(n/c\) vertices. Consequently a graph with no independent set of size \(\delta n\) cannot be properly colored using \(c\) colors whenever \(1/c\ge\delta\) (with the usual integer rounding interpreted carefully).
What is known
The protected Family 106 catalogue identifies one manuscript: Hardness of finding large independent sets in three-colorable graphs.
The pinned publisher overview states a stronger reduction claim: for every fixed \(0<\delta<1/3\), a deterministic polynomial-time reduction from 3SAT constructs simple unweighted graphs such that:
- If the input formula is satisfiable, the output graph is three-colorable.
- If the input formula is unsatisfiable, the output graph has no independent set with at least \(\delta n\) vertices, where \(n\) is its number of vertices.
For any fixed integer \(c\ge3\), choose a constant \(\delta\) with \(0<\delta<\min(1/3,1/c)\) (for example, \(\delta=1/(2c)\)). A proper coloring with \(c\) colors would yield an independent set of at least \(n/c>\delta n\) vertices, contradicting the NO-case promise. Thus the stated reduction, if correct, implies NP-hardness of producing a valid coloring with \(c\) colors of a promised three-colorable graph for each fixed \(c\).
The quantifier “fixed” is essential. This is not a claim of hardness against every number of colors that grows with input size, nor a promise that all graphs in the reduction are three-colorable.
GCL verification state
The source lock is openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The pinned catalogue identifies one PDF, and the overview states the exact \(\delta\) range, polynomial-time reduction source, graph type, and YES/NO gap.
GCL has not independently checked the construction, its size and running-time bounds, its completeness and soundness, or how integer rounding enters the independent-set threshold. No Family 106-specific Lean compilation receipt, Comparator result, proof-semantic audit, or MATHCERT certificate is asserted.
What remains
Read the pinned manuscript and identify the exact theorem statement and reductions. Confirm that the graph is genuinely simple and unweighted, with no covert gadget weights or parallel edges; verify deterministic polynomial size for each fixed \(\delta\). Audit the preservation of three-colorability on satisfiable inputs and independent-set bounds on unsatisfiable inputs.
Check precise integer rounding in \(\alpha(G)<\delta n\) versus “no independent set of size \(\delta n\),” and extract the uniformity assumptions if \(\delta\) is part of the input rather than fixed in advance. Reconstruct the coloring-hardness corollary and identify which complexity-theoretic premise is invoked.
Finish mathematical Markdown/HTML regression, source-critical editorial review, and protected merge/readback. Editorial acceptance alone is not mathematical certification.
Sources and claim boundaries
Boundary: NO_CERTIFICATION. The hardness claims are publisher-reported and await independent verification.
Indexed primary manuscript paths:
- Hardness of finding large independent sets in three-colorable graphs —
preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026.pdf