Hardness of coloring three-colorable graphs

← All digests

Family 106 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-08

Suppose a graph can be colored with three colors, but nobody gives you the coloring. Would allowing ten colors make the task easy? What about a thousand? Family 106 claims a stronger obstacle than the failure of every fixed larger palette: it gives a hardness gap between graphs that are entirely three-colorable and graphs whose independent sets occupy only a tiny fixed fraction of their vertices.

1. The question

Graph coloring is a model for separating incompatible objects. Vertices might represent jobs, and an edge might mean that two jobs cannot share a time slot. A proper coloring assigns different colors to adjacent vertices.

If three colors suffice, a valid three-way separation exists. The algorithmic challenge is to discover a separation from the edges alone. We can relax the output requirement by allowing $c$ colors, where $c$ is any fixed number larger than three.

An even weaker-looking task is to find one large group with no internal conflicts. Such a group is an independent set. Every three-coloring partitions the graph into three independent sets, so one of them contains at least a third of the vertices. The manuscript studies how hard it is to exploit that guarantee when the coloring itself is hidden.

2. Background and essential definitions

Coloring and independent sets

Let $G=(V,E)$ be a nonempty finite graph and write $n=|V|$. An independent set $I\subseteq V$ contains no adjacent pair. Its largest possible size is the independence number $\alpha(G)$.

The chromatic number $\chi(G)$ is the smallest number of colors in a proper coloring. In any proper $c$-coloring, at least one color class has size at least $n/c$, by the pigeonhole principle. Hence

$$\alpha(G)\ge\frac{n}{\chi(G)}, \qquad \chi(G)\ge\frac{n}{\alpha(G)}.$$

The ratio $\alpha(G)/n$ is the independence density. A graph with small independence density has no large conflict-free group anywhere, not merely a complicated obstruction inside a small region.

A graph is simple if it has no loops or repeated edges, undirected if edges have no orientation, and unweighted if vertices and edges have no numerical costs. The claimed reduction produces graphs of this ordinary kind.

A promise is information, not a supplied solution

The coloring search problem promises that $\chi(G)\le3$, but supplies only the graph. If the actual three-coloring were part of the input, producing a $c$-coloring for $c\ge3$ would be immediate: reuse it.

For hardness, the paper uses a decision gap. The input is promised to belong to one of two classes: graphs that are three-colorable, or graphs with very small independence density. Graphs between those classes do not have to be classified.

A deterministic polynomial-time reduction from 3SAT maps satisfiable Boolean formulas to the first class and unsatisfiable formulas to the second. Since 3SAT is NP-complete, an efficient distinction would imply $\mathsf P=\mathsf{NP}$. Here polynomial time means a bound by a fixed power of the input length, rather than a running time that is merely finite.

There is no assertion that one graph is simultaneously three-colorable and has independence density below one third. Those are the two alternatives of the reduction.

3. Development history and previous partial results

The gap between knowing a small coloring exists and finding even a larger one has been studied for decades. Khanna, Linial, and Safra established hardness of four-coloring three-colorable graphs; Guruswami and Khanna later gave a different proof and additional variants. This already showed that allowing one extra color does not generally remove the difficulty.

The algebraic theory of promise constraint satisfaction provided a further advance. Barto, Bulín, Krokhin, and Opršal proved hardness of $(2k-1)$-coloring a $k$-colorable graph. Setting $k=3$ gives the five-color barrier. The theory studies which operations preserve the allowed constraint relations, connecting algebraic structure with computational complexity.

In 2020, Guruswami and Sandeep showed that the perfect-completeness $d$-to-one Games Conjecture, for any fixed $d\ge2$, implies hardness of coloring three-colorable graphs with every fixed larger palette. This made the coloring question depend on a broader family of constraint-game hypotheses.

On September 14, 2026, Fei, Minzer, and Wang posted a perfect-completeness four-to-one games theorem and stated the fixed-palette coloring consequence. Their result is an important predecessor to the September 24 manuscript in this family. The basic constant-palette consequence is therefore not presented here as first obtained by family 106.

The new manuscript emphasizes the stronger independent-set statement. Earlier routes to small independence density with perfect completeness gave a larger promised palette, while related work on almost-three-colorable graphs allowed a small fraction of vertices to be discarded. Dinur, Khot, Perkins, and Safra, for example, studied independent-set hardness under that almost-colorable promise. Keeping the entire yes-instance three-colorable while obtaining arbitrarily small fixed independence density in the no-instance is the claimed advance.

4. What the new manuscripts claim

Theorem 1.1 states that, for every fixed real $0<\delta<1/3$, there is a deterministic polynomial-time reduction taking a 3SAT formula $\varphi$ to a nonempty simple undirected unweighted graph $G_\varphi$ such that

$$\begin{aligned} \varphi\text{ satisfiable}&\quad\Longrightarrow\quad \chi(G_\varphi)\le3,\\ \varphi\text{ unsatisfiable}&\quad\Longrightarrow\quad \alpha(G_\varphi)<\delta\,|V(G_\varphi)|. \end{aligned}$$

The output explicitly lists the graph. The constants and polynomial degree may depend on the fixed $\delta$, but not on the formula. The satisfying-case coloring covers every vertex and is not supplied with the graph.

Why this implies every fixed-palette barrier

Fix an integer $c\ge3$ and choose

$$0<\delta<\min\{1/3,1/c\}.$$

In the good case, the graph is three-colorable. In the bad case, a proper $c$-coloring would contain an independent color class of size at least $n/c>\delta n$, which the gap excludes. Thus the claim implies hardness of distinguishing three-colorable graphs from graphs that are not $c$-colorable.

For example, to rule out a fixed palette of 100 colors, it is enough to use any fixed $\delta<1/100$. The palette may be enormous, provided it is fixed before the input size grows.

The same gap explains independent-set search hardness. An algorithm guaranteed to find an independent set of size at least $\delta n$ on every three-colorable graph could be run on the reduction’s output. Check that its output is independent and large enough. A yes-instance must pass; a no-instance cannot. The output check is easy even though finding the set is claimed to be hard.

5. Why the advance matters

High chromatic number alone can reflect a small difficult core. Add many isolated vertices to a graph: its chromatic number stays the same, but the isolated vertices form a large independent set. Therefore, “requires many colors” does not imply “has no large independent set.” The latter is a stronger and more global obstruction.

The claimed gap preserves an exact, attractive structure in the good case while eliminating even a weak density guarantee in the bad case. This can matter in reductions where finding one substantial independent set is already useful, without requiring a full coloring.

Importance: 4/5, provisional. Combining three-colorability of every yes-instance vertex with arbitrarily small fixed independent-set soundness would be a major advance in graph approximation. The rating rests on that stronger gap and the direct reduction, while recognizing that the constant-palette coloring consequence also has an earlier route.

6. The main idea

Begin with local consistency tests

The source problem is Label Cover, a bipartite constraint system. Each left and right vertex receives a label; an edge specifies a function that maps the left label to the required right label. Standard PCP and repetition results provide a gap between completely satisfiable instances and instances where every labeling succeeds on only a small fraction of edges.

The construction must turn a satisfying labeling into a proper three-coloring. In the reverse direction, any large independent set in the constructed graph must reveal enough consistent source labels to violate the source soundness bound. These two goals guide the geometry and the analysis.

Put the colors on a circle

The paper associates encoded answers with phases on the circle

$$\mathbb T=\mathbb R/\mathbb Z.$$

A phase can be represented by a number in $[0,1)$, with 0 and 1 identified. Its distance from another phase is the shorter circular distance. Split the circle into the three half-open intervals

$$[0,1/3),\qquad[1/3,2/3),\qquad[2/3,1).$$

Each interval can represent a color. Two phases more than one third of a turn apart cannot lie in the same interval.

At each tuple of source questions, an encoded point assigns a phase to every possible product answer. Projection maps between questions identify corresponding coordinates. The paper links these spaces and defines distances through the links, using a pseudometric: different descriptions may have distance zero when the construction identifies them.

A genuine satisfying assignment selects one answer coordinate consistently throughout these spaces. Evaluating that coordinate assigns a circle phase to each graph vertex. The construction compares points with half-turn shifts and chooses its edge threshold so that adjacent vertices receive phases more than one third apart. The three intervals then give a proper coloring.

Although continuous geometry describes the idea, the output graph uses fixed finite rational data. Random sampling in the analysis is expanded into explicitly listed vertices, so the stated reduction itself is deterministic.

A large independent set reveals a few influential labels

For the opposite implication, the paper converts an independent set into bounded functions on the phase spaces. They obey a Lipschitz condition: moving the input by a small distance changes the output by at most a fixed multiple of that distance. They also change sign under a half-turn shift.

A continuous approximation theorem supplies a function depending on only boundedly many coordinates. Such a function is called a junta. Here coordinates correspond to candidate answers, so this yields short lists of possible source labels. Crucially, the list-size bound does not grow with the full dimension of the phase space.

Local approximations are not automatically compatible. A projection can merge coordinates, and lists constructed in neighboring layers may depend on different information. The manuscript builds lists for small chains of questions and projects them into a common answer space. Too many intersections between suitably separated lists would supply compatible labels for a source constraint.

The remaining alignment argument and a multilevel choice of coefficients limit how much a function can depend on many such lists at once. Combined with the bound on influential coordinates, this forces the independent-set density to be small in the bad case. The circle supplies the three-colorable good case; the coordinate-decoding argument supplies the stronger bad-case obstruction.

7. Scope, limitations, and open questions

The soundness density $\delta$ and palette size $c$ are fixed constants. The running-time polynomial is allowed to depend on them. One cannot substitute $c=\log n$, or a density shrinking with $n$, and infer the same hardness statement without controlling that dependence.

This leaves room for polynomial-time algorithms using a number of colors that grows with the graph size. For example, Kawarabayashi, Thorup, and Yoneda’s 2024 work gave a bound with a small positive power of $n$, up to logarithmic factors. Fixed-palette hardness and such growing-palette upper bounds address different regimes.

The graph is promised to have a three-coloring; the theorem does not make checking a supplied coloring difficult. Checking that every edge has distinct endpoint colors takes time proportional to the graph description. Existence, discovery, and checking a proposed solution are different tasks.

Finally, these are worst-case NP-hardness claims with the usual consequence under $\mathsf P\ne\mathsf{NP}$. Structured graph families, practical heuristics, and quantitative bounds when the palette grows with input size require separate analysis.

8. Sources and further reading

Hardness of finding large independent sets in three-colorable graphs, credited to OpenAI, September 24, 2026. Theorem 1.1 gives the independent-set gap, Corollary 1.2 gives the coloring consequence, and Sections 1.1–1.2 explain the relation to earlier work and the construction.

Historical sources are linked in Section 3. Optional background: graph coloring, independent sets, and Lipschitz continuity. Family 105 explains the related perfect-completeness two-to-one games claim.

Source revision: adc7f1241b42. Sources consulted: October 8, 2026. Citation data: BibTeX.

See the series’ AI declaration for authorship and review status. Back to the family index.