Hardness of coloring three-colorable graphs

The explanation

Take a triangular prism. It is two triangles, with each corner joined to the matching corner of the other. That gives 6 corners and 9 lines. Try to paint the corners so that joined corners always get different colors. Three colors work, in 12 different ways. Two colors never work, because each triangle needs three.

Mathematicians call such a drawing a graph. The corners are vertices and the lines are edges. A proper coloring gives joined vertices different colors. An independent set is a group of vertices with no edge between any two of them. The prism's largest independent set has 2 vertices, one third of its 6. That is no accident. Each color class of a proper coloring is an independent set. With three colors, one class must hold at least a third of the vertices.

Now scale up. A three-colorable graph with 3000 vertices always has an independent set of at least 1000. Picture a second graph with 3000 vertices whose largest independent set has fewer than 300. That graph cannot be properly colored with 10 colors. Ten classes of at most 299 vertices cover at most 2990 vertices. The two graphs differ sharply. Yet this paper proves that telling them apart is NP-hardSource 1.

NP-hard means this: a fast method for the task would speed up every problem in a large class called NP. The paper shows this by translation from 3SAT. A 3SAT formula is a logic puzzle: many short rules, each about three true-or-false switches. The question is whether some setting of the switches obeys every rule. For each fixed fraction δ between 0 and 1/3, the paper builds a fast, fixed recipe. It turns a solvable formula into a three-colorable graph. It turns an unsolvable formula into a graph whose independent sets all hold fewer than δ times the verticesSource 2. With δ = 1/10, these are exactly the two graphs above. The ceiling 1/3 is natural, since three-colorable graphs always have a third.

A weaker coloring version follows. For any fixed number of colors c, at least 3, finding a proper c-coloring of a three-colorable graph is NP-hard. That question has a long history. In 2000, Khanna, Linial and Safra proved hardness for four colors. Barto, Bulín, Krokhin and Opršal reached five colors, in a 2021 paper. In 2020, Guruswami and Sandeep showed that every fixed palette would follow from an unproved conjecture about certain puzzles. In September 2026, Fei, Minzer and Wang proved a version of that conjecture. Combined with earlier reductions, it settles the coloring question for every fixed palette. So the coloring statement here is not new. The paper says it recovers itSource 3.

The new part is the small independent sets, together with three colors for the whole graph. Earlier work got one half without the other. Fei, Minzer and Wang get small independent sets, but only for graphs promised to be eight-colorable. The step that shrinks the palette to three loses the independent-set guarantee. Dinur, Mossel and Regev got both halves in 2009, but only by assuming an unproved conjecture. Braverman, Khot, Lifshitz and Minzer did the same from a different conjecture. Dinur, Khot, Perkins and Safra reached a density of 1/9 in 2010. But their easy case lets a few vertices fall outside the coloring.

The proof gives each vertex a set of positions on a circle. In the solvable case, joined vertices end up more than a third of a turn apart. Cutting the circle into three equal arcs then colors every vertexSource 4,Source 5. The hard direction is the reverse. A large independent set must reveal a good solution to the logic puzzle. The standard tool for this approximates functions by a few coordinates. That approximation can break when the puzzle glues coordinates togetherSource 6. The paper answers with new machinery of its own. It picks key coordinates for whole stretches of the puzzle at once. It adds fresh random rotations at every layer. A new alignment argument, drawing on game theory and Ramsey theory, makes labels line up across layers. Random tests at several scales then turn this into the small independent-set bound. The paper proves every piece itselfSource 7.

The result has limits. Each fraction δ gets its own recipe. Its running time is polynomial, but the power may depend on δSource 8. The paper claims no common running time as δ shrinks toward zeroSource 9. It also says nothing new about how many colors fast methods need. For n vertices, Bansal, Huang and Lee use on the order of n to the power 0.19539 colors. Later preprints report smaller powers. A wide gap remains between a fixed number of colors and such growing counts.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the recipe from 3SAT, both promises, and a running-time bound that counts the whole output. The Lean scope note does not list the coloring consequence separately, though it is a short step in the paper. No specialists have published a review yet.

What it doesn't show. This does not say how many colors a fast method needs, and the coloring consequence was already known.