1 · The essentials
A graph is a collection of points with links between some pairs. Coloring it means giving each point a color so that linked points have different colors. The manuscript studies graphs for which three colors are enough, even though a suitable coloring is not supplied. Its main result says that finding a coloring remains computationally hard even when any fixed larger number of colors is allowed. The stronger statement concerns groups of points with no links between them: it is hard to distinguish graphs that can be colored with three colors from graphs where every such group is small. Here, “small” means below a chosen fraction of all the points, with that fraction fixed between zero and one third. The main result has a Lean formalization; this is a statement about computational difficulty, not about whether a coloring exists.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine assigning people to rooms when certain pairs must be kept apart. Even if you are assured that three rooms suffice, finding a valid assignment can remain hard when you allow any fixed number of rooms greater than three. A group that can share one room corresponds to a set of points with no links between them.
Why it matters
The result separates the existence of a very economical coloring from the difficulty of finding even a less economical one. Its stronger independent-set formulation connects two tasks: assigning colors and finding large groups with no internal links. The repository states the hardness for simple unweighted graphs, so it does not depend on extra numerical weights.
2 · Going further
The precise distinguishing problem fixes a constant . One case consists of three-colorable graphs; in the other, every independent set has size strictly less than , where is the number of vertices. The repository summary states that a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs with these properties: satisfiable inputs give three-colorable graphs, and unsatisfiable inputs give graphs with no independent set of size at least .
The stated consequence is that, for every fixed integer , finding a proper -coloring of a three-colorable graph is NP-hard. The connection is that each color class is an independent set: a proper coloring cannot place linked vertices in the same class. Choosing makes the small-independent-set case incompatible with a -coloring, whose classes would have to cover all vertices.
The supplied abstract states the distinguishing theorem and its coloring consequence, but does not describe how the reduction is constructed or give the main technical argument. The main manuscript is marked as Lean-formalized. Only one manuscript is supplied, so there are no companion-manuscript relationships to describe, and the source gives no further historical context.
Useful notions
- Graphs and proper colorings
- Independent sets
- Fixed constants versus input size
- Polynomial-time reductions
- 3SAT and NP-hardness
What was known before / what is new
Before
The supplied text does not identify earlier hardness bounds or previous methods for this problem. Its starting setting is the task of coloring a graph when three colors are known to suffice, without being given such a coloring.
New
The main result gives NP-hardness of distinguishing three-colorable graphs from graphs whose independent sets all have size below , for every fixed . It yields hardness of finding a proper -coloring for every fixed integer . The repository additionally specifies a deterministic polynomial-time reduction from 3SAT with simple unweighted output graphs.
Limits and assumptions
The fraction must be fixed and strictly between zero and one third, and the number of allowed colors must be a fixed integer at least three; the source does not state a result for a number of colors that grows with the input. The distinction concerns two specified classes of graphs, not a classification of every graph. The main result has a Lean formalization, but the supplied text does not detail which implementation-level reduction claims or accompanying consequences are included in its scope. No remaining open problems are identified in the source.
Mini glossary
- Proper coloring —
- An assignment of colors to vertices in which the endpoints of every edge have different colors.
- Three-colorable graph —
- A graph that admits a proper coloring using at most three colors.
- Independent set —
- A set of vertices with no edges joining any pair within the set.
- Polynomial-time reduction —
- A transformation between computational problems that preserves the relevant answers and runs in time bounded by a polynomial in the input size.
- NP-hardness —
- A complexity classification indicating that solving the problem would allow one to solve every problem in NP through polynomial-time reductions.
- 3SAT —
- The problem of deciding whether a Boolean formula expressed as clauses of three literals has a satisfying assignment.
Keywords : Graph coloring · Independent sets · NP-hardness
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed , a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size otherwise, where n is the number of vertices.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Hardness of finding large independent sets in three-colorable graphs
24/09/2026We prove that, for every fixed , it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c-coloring of a three-colorable graph is NP-hard.