Hardness of coloring three-colorable graphs at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

Hardness of coloring three-colorable graphs

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.6 out of 5 (4,992 votes)

>>> How to Play <<<

Hardness of coloring three-colorable graphs. It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed $0\lt \delta\lt 1/3$, 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 $\delta n$ otherwise, where n is the number of vertices.

>>> Level Select <<<

LEVEL 1 Hardness of finding large independent sets in three-colorable graphs

released 2026-09-24 | 3 theorems · 6 lemmas · 10 proofs · 9,676 words | PLAY LEVEL 1 » (pdf)

We prove that, for every fixed $0\lt \delta\lt 1/3$, 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.

More Theoretical computer science Games!
Approximate counting and the perfect-matching entropy conjecture	Approximate counting of common integer polymatroid bases	Sampling and counting contingency tables with arbitrary margins	Uniform identity testing for noncommutative formulas
Uniform sparsest cut: hardness and semidefinite gaps	Unbounded bin-packing gaps and the modified integer round-up conjecture	The Courtade–Kumar and Hellinger conjectures	Almost-linear-time exact matching in general graphs

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600