OpenFrontiers
Join
← Back to the index
OP-12036OpenGraph theory

Chromatic number of the plane (C27aC_{27a})

Chromatic number of the plane: determine C27aC_{27a} or improve its bounds; the repository records 5 (lower) and 7 (upper).

MSC 05C15 · Coloring of graphs and hypergraphsMSC 52C10 · Erd?s problems and related topics of discrete geometry

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C27C_{27} is the chromatic number of the plane, usually denoted χ(R2)\chi(\mathbb R^{2}) (the Hadwiger–Nelson problem).

Equivalently, let U2U_{2} be the unit-distance graph on R2\mathbb R^{2}: its vertex set is R2\mathbb R^{2}, with an edge between distinct points x,y∈R2x,y\in\mathbb R^{2} iff ∥x−y∥2=1\|x-y\|_{2}=1. Then

C27 := χ(R2) := χ(U2),C_{27} \ :=\ \chi(\mathbb R^{2}) \ :=\ \chi(U_{2}),

i.e. C27C_{27} is the smallest integer kk such that there exists a map c:R2→{1,…,k}c:\mathbb R^{2}\to\{1,\dots,k\} satisfying c(x)≠c(y)c(x)\neq c(y) whenever ∥x−y∥2=1\|x-y\|_{2}=1.

It is known that

5 ≤ C27 ≤ 7.5\ \le\ C_{27}\ \le\ 7.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • The main open question is whether C27∈{5,6,7}C_{27}\in\{5,6,7\}.

  • Finite reduction (with choice). Since C27≤7C_{27}\le 7, the de Bruijn–Erdős theorem [dBE1951] implies (assuming the axiom of choice) that C27C_{27} is attained by some finite unit-distance graph in the plane. In particular, under choice, C27C_{27} equals the maximum chromatic number among finite unit-distance graphs in R2\mathbb R^{2}.

  • Known 55-chromatic unit-distance graphs. de Grey’s original construction had 15811581 vertices [deG2018]. Subsequent computer-aided work produced substantially smaller 55-chromatic examples; see e.g. [Heu2018] and the Polymath16 project page.

  • Witness sizes for 77 colors. If C27=7C_{27}=7, then there must exist a finite 77-chromatic unit-distance graph. Quantitative lower bounds on the minimum number of vertices needed for such a graph are known; see [Pri1998].

  • Set-theoretic issues. The de Bruijn–Erdős reduction uses choice, and without it chromatic phenomena for related distance graphs can depend on the axioms of set theory; see [SS2003], [SS2004].

  • Wikipedia page on the Hadwiger–Nelson problem

  • Polymath16 page

References (from the repository page)

  • [CR2017] Cranston, Daniel W.; Rabern, Landon. The fractional chromatic number of the plane. Combinatorica 37 (2017), no. 5, 837–861. arXiv:1501.01647

  • [dBE1951] de Bruijn, N. G.; Erdős, P. A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math. 13 (1951), 371–373.

  • [deG2018] de Grey, Aubrey. The chromatic number of the plane is at least 5. Geombinatorics 28 (2018), no. 1, 18–31. arXiv:1804.02385

  • [EI2020] Exoo, Geoffrey; Ismailescu, Dan P. The chromatic number of the plane is at least 5: A new proof. Discrete & Computational Geometry 64 (2020), 216–226. arXiv:1805.00157

  • [Had1945] Hadwiger, Hugo. Überdeckung des Euklidischen Raumes durch kongruente Mengen. Portugaliae Math. 4 (1945), 238–242.

  • [Heu2018] Heule, Marijn J. H. Computing small unit-distance graphs with chromatic number 5. arXiv:1805.12181 (2018).

  • [MM1961] Moser, L.; Moser, W. Solution to Problem 10. Canadian Mathematical Bulletin 4 (1961), 187–189.

  • [Pri1998] Pritikin, David. All unit-distance graphs of order 6197 are 6-colorable. J. Combin. Theory Ser. B 73 (1998), no. 2, 159–163.

  • [SS2003] Shelah, Saharon; Soifer, Alexander. Axiom of choice and chromatic number of the plane. J. Combin. Theory Ser. A 103 (2003), no. 2, 391–397.

  • [SS2004] Soifer, Alexander; Shelah, Saharon. Axiom of choice and chromatic number: examples on the plane. J. Combin. Theory Ser. A 105 (2004), 359–364. DOI: 10.1016/j.jcta.2004.01.001.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 5; best known upper bound 7. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
77 [Had1945], [CR2017] A periodic 77-coloring obtained from a tiling of the plane by small regular hexagons (historically attributed to Isbell, 1950).

Known lower bounds

Bound Reference Comments
33 Trivial An equilateral triangle of side length 11 forces three colors.
44 [MM1961] Moser spindle: a 77-vertex unit-distance graph with chromatic number 44.
55 [deG2018] First proof that χ(R2)≥5\chi(\mathbb R^{2})\ge 5, via an explicit finite unit-distance graph.
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Chromatic number of the plane ($C_{27a}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.