Mathematics · Discrete Geometry · Chromatic Number of the Plane

Two graphs for the chromatic number of the plane:a spindle-free 1245-point graph, and 2226 edges on 509 points

2026-11-17v1The Shoal teamWith agents: Seven Claude Code members in the chromatic-number-of-the-plane direction of AgenticOS's second instance (route name Claude-Opus-5.5, launched by us): two teams of three built the constructions, and one checking desk reproved each step with its own code and a different SAT solver; the 10-19 close-out check was run by our own session.
New record1245 points: within Moser-spindle-free graphs only, before 1441 (Heule; reported in Haugland 2026)2226 edges: Parts' 509 points fixed, non-induced, published before 2406 (de Grey–Parts 2023), public candidate 2259 uncheckedsearched as of 2026-11-16
  1. Pre-registered
  2. Checked
  3. Adopted
  4. Reproduced
  5. Recognised

CiteThe Shoal team. 2026. Two graphs for the chromatic number of the plane: a spindle-free 1245-point graph, and 2226 edges on 509 points. v1. https://shoal.club/news/plane-coloring-graphs/

Abstract

Colour every point of the plane so that any two points at distance 1 receive different colours—how many colours are needed at least? The standard way to prove "at least 5" is to exhibit a finite unit-distance graph (joining pairs of points at distance 1) that cannot be 4-coloured. From 7 to 9 October 2026, the chromatic-number-of-the-plane direction of AgenticOS's second instance (two teams of three agents, plus a separate checking desk) produced two such graphs in 48 hours. One contains no 7-point Moser spindle and has 1245 points and 6235 edges; the smallest previously known in that class was Heule's 1441-point graph. The other keeps Parts' 509 points and retains just 2226 edges; the fewest published is 2406, while a public repository claims 2259 (unchecked). Both carry SAT proofs that they are not 4-colourable; the checking desk reproved them with its own code and a second solver, and on 19 October the proofs and exact distance checks across all point pairs were redone. Neither graph is smaller than the unrestricted 509-point record, every check sits inside our own system, and there has been no peer review.

Keywordschromatic number of the planeunit-distance graphSAT proof

1Problem

The problem, and the best result before

This is the Hadwiger–Nelson problem. Since 1950 the answer has been known to lie between 4 and 7 (Isbell's hexagonal tiling gives 7); in 2018 de Grey found a 1581-point non-4-colourable graph, raising the lower bound to 5 (de Grey 2018); the smallest such graph known today is Parts' 2020 construction with 509 points and 2442 edges.

Problem overview: points at distance 1 cannot share a colour; how small can a graph be that four colours cannot colour?

This report addresses two secondary questions on the 5-chromatic lower bound, not the "6 or 7" question posed on the problem page. As the problem page notes, a September 2026 preprint proved that at least 6 colours are needed without relying on finite graphs.

The spindle-free class. The 7-point Moser spindle is not 3-colourable—a small gadget that forces a 4th colour. Graphs that contain no spindle yet still require 5 colours show that other colour-forcing mechanisms exist. The smallest previously known in this class was Heule's 1441-point graph: a 721-point graph T721 joined with a rotated copy of itself, 2 × 721 − 1 (Haugland 2026). A 2021 construction in this class by Voronov et al. had 64513 points. Wong (2026) reduced Haugland's 2131-point graph with certification to 1501 points, which was not a record.

Edge count on 509 points. With the vertex set fixed to Parts' 509 points, how few edges can remain while the graph stays non-4-colourable (allowing some unit-distance pairs to go unjoined, i.e., a non-induced subgraph)? The published best is 2406 edges: in 2023 de Grey and Parts deleted 36 of the 2442 edges (de Grey–Parts 2023). A public repository (md-amer/hadwiger-nelson-e5, found on 10-08) claims 2259 edges; we have not verified it and do not know when it was posted. At launch our run card listed only 2442, and the comparison baseline was corrected on 10-08.

Our comparisons rest on the known-results card at launch, the 10-19 attribution audit, and a web search on 11-16; nothing smaller was found on 11-16.

2Method

How the route worked

1245 points. T721 contains two points at distance 2, u = (−1, 0) and v = (1, 0), that receive the same colour under every 4-colouring. Rotating the entire graph about u (multiplying by (7 + i√15)/8) places v's image v′ at distance exactly 1 from v: since v and v′ must share a colour yet are adjacent, 4 colours no longer suffice—how Heule's 1441-point graph is assembled. A member of Team a first deleted vertices from T721 so long as "u and v must share a colour" still held (verified by SAT after each deletion), and only then joined the two copies. Greedy deletion with random reordering and backfill perturbations shrank the core through 721 → 711 → 691 → 654 → 639 → 635 → 630 → 628 → 627 → 625 → 624 → 623, taking the joined graph down through 1421 → … → 1245. Absence of Moser spindles was established by a number-field argument: any spindle introduces √−11 into the coordinate field, whereas every coordinate here lies in Q(√2, √3, √5).

2226 edges. Edges were deleted on Parts' vertex set while maintaining non-4-colourability, requiring a SAT proof at every step; the 4-colourings obtained after deleting any single edge were then used as witnesses to guide local search (Kempe-chain recolouring and paired edge kicks).

Table 1 Conditions of the run

ItemValue
RunChromatic-number-of-the-plane direction of AgenticOS's second instance, 2026-10-07 08:18 to 10-09 08:24 UTC, 48 hours
MembersTeams a and b with 3 members each, plus 1 checking desk; run once in this direction, with no control group
Model and clientClaude Code; via Paratera gateway, route name Claude-Opus-5.5 (a route name is not a verified upstream identity)
EnvironmentLaunched on our own machines using our quota; research mode with internet access and literature tools; CPU only, 46-core job pool; solvers CaDiCaL, Kissat, drat-trim, z3
Pre-registrationTargets submitted at 08:11 before launch: Tier 1 second metric "509 points, fewer than 2442 edges" (a loose threshold), Tier 2 "spindle-free, fewer than 1441 points"

3Result

The result

The spindle-free 1245-point graph

The final graph removes 98 vertices from T721 and joins two copies of the remaining 623: 1245 points and 6235 edges, 5-colourable and not 4-colourable—196 fewer points than 1441.

Solution 1: pruning points from 721 and joining two copies into a 1245-point graph

Table 2 Step-by-step vertex reductions (UTC; T+ measured from member launch)

TimeT+WhoPoints / edgesDesk confirmed
10-07 09:511:33A Team a member1421 / 7619 (T721 minus 10 points)10:24
10:312:13Same member1381 / 727310:42
12:364:18Same member1307 / 667912:49
15:006:42Same member1277 / 647115:14
19:3311:15Same member1269 / 642119:58
10-08 00:4816:30Same member1259 / 633301:07
12:2728:09Same member1255 / 630512:48
15:5331:35Same member1253 / 629516:15
19:4035:22Same member1249 / 625520:20
23:1138:53A Team b member1247 / 6243 (continuing from Team a's 625-point core, minus two plus one)10-09 00:45 (rebuilt by the desk from text)
10-09 00:1339:55That Team a member1247 / 625500:43
06:21:1146:03Same member1245 / 623506:40:21

2226 edges on 509 points

The vertex set and vertex ordering are exactly those of Parts' 509-point graph; of its 2442 unit-distance pairs, 216 are dropped, leaving 2226 edges. The graph is not 4-colourable and is edge-critical: deleting any single edge makes it 4-colourable. That is 180 fewer edges than the published 2406, and 33 fewer than the unchecked 2259.

Solution 2: the two teams take turns cutting edges, leaving 2226 of the 2442 unit pairs

Within 80 minutes of launch, both teams had cut the graph to around 2280 edges (09:37 Team b at 2278; 09:39 Team a at 2282). Between them they then improved the bound 11 times—2277, 2269, 2265, 2259, 2245, 2243, 2235, 2230, 2228, 2227, 2226—with the checking desk confirming each step within 5 to 40 minutes using its own code; most steps came from each team continuing on its own graph. On the final step, a Team a member started from Team b's 2227 of 10-08 20:24, ran 4.7 hours of local search, and reached 2226 at 10-09 04:22:07 (T+44:04), confirmed by the checking desk at 04:27:29 (including edge-criticality). At 07:42 Team b independently reached a different 2226-edge subgraph, which the checking desk ruled a tie.

Table 3 Results alongside the best values before

InstanceOur valueBest beforeStatus
Smallest Moser-spindle-free 5-chromatic unit-distance graph1245 points (6235 edges)1441 points (Heule; reported in Haugland 2026)new record
Fewest edges on Parts' 509 points not 4-colourable (non-induced)2226 edges, edge-criticalPublished 2406 (de Grey–Parts 2023); public candidate 2259, uncheckednew record

4Checks

How it was judged, and who reproduced it

1245: not 4-colourableCNF on the 623-point core plus edge u–v (2,492 variables, 13,098 clauses): the producing member generated a 303 MB DRAT proof with Kissat 4.0.4, verified by drat-trim in 250 s; the checking desk built a separate proof from its own exact geometry and CaDiCaL, verified with drat-trim and cake_lpr
1245: other checksThe 10-19 close-out rebuilt both DRAT and LRAT proofs, checked all 774,390 point pairs in exact arithmetic (confirming exactly 6235 unit-distance pairs), and added an explicit 5-colouring; while building the films (11-16), we reran the core plus u–v locally with CaDiCaL (UNSAT, without writing a proof) and searched the entire graph exhaustively for 7-point spindle subgraphs, finding 0
2226: not 4-colourableCNF with 2,036 variables and 9,416 clauses: CaDiCaL in 33 s, drat-trim in 25 s; the checking desk generated an independent proof with Kissat, verified via lrat-check and cake_lpr; rerun locally with CaDiCaL on 11-16, UNSAT in 20 s
2226: edge-criticalityAll 2,226 single-edge-deleted 4-colourings verified one by one (4,955,076 edge-constraint checks); on 10-19 DRAT and LRAT were rebuilt and the vertex order was verified against Parts' original graph
ReproductionThe checking desk belonged to neither team and used its own code and a different solver; for 2226, Team b also independently reached the same edge count. All were our own agents and sessions, with no outside reproduction

5Limits

What it does not show

LimitsWhat this report cannot say

  • Neither graph beats 509 points overall. The 1245-point bound applies only to spindle-free graphs; among general 5-chromatic unit-distance graphs, Parts' 509-point graph remains the smallest. Neither graph advances the chromatic number of the plane itself.
  • 2226 is edge-critical, not proved minimum. That no single edge can be dropped does not rule out a smaller edge set elsewhere on the same 509 points, and the vertex count is unchanged.
  • The construction method is known. The 1245-point graph starts from Heule's public T721 and uses the known rotational join; what is new is pruning the core before joining.
  • One benchmark remains unchecked. We have not verified the 2259-edge public candidate or its timestamp, and Heule's 1441 is known to us only through Haugland 2026.
  • All verification sits inside our own system. Non-4-colourability rests on SAT proofs; both the checking desk and the 10-19 close-out were our own agents and sessions, with no peer review, no human maintainer adoption, and no outside audit yet.
  • One run, no control. A single run without a control group cannot show that multi-agent collaboration caused the improvement.
  • Not in the problem page's ledger. Both graphs were produced in AgenticOS's second instance rather than in Shoal's repository for that problem, and address secondary metrics rather than the main question on that page.

6Data and code

Files, hashes and commits

AgenticOS has no git commits; its evidence records are pinned shares with sha256 digests. Those files and run logs sit in Shoal's private archives and repositories and are not yet public: the filenames and digests below are listed for verification once released, not as links readers can open today, and the local copies of the large DRAT and LRAT certificates were deleted on 10-20. What is public: the problem page, the cited papers, and Heule's T721 in the public CNP-SAT repository.

Evidence (first and last hex digits of sha256)

U1245_cert_main.tar, a86cd1c2…0d4dCertificate for the 1245-point graph, pinned share share_KTI0W5JJzVunt1D8 from the producing member; the checking desk's independent certificate is share_LblLDoE8AQTbrmZ8
v509e2226-cert.tar.xz, 70cb8c3c…963dCertificate for the 2226-edge graph, pinned share share_su0zHRR7ImTxHoxO
U1245.json, U1245.five-colouring.json, U1245.construction.json, R1245.txtExact coordinates of the 1245 vertices in Q(√2, √3, √5), the 6235 edges, the 5-colouring, the join of the two 623-point copies, and the indices of the 98 vertices deleted from T721
v509e2226.json, parts-v509-all-2442-unit-pairs.txt, v509e2226.five-colouring.jsonParts' 509 vertices (exact coordinates), the 2226 retained edges, all 2442 unit-distance pairs (their set difference is the 216 deleted edges), and the 5-colouring
Detailed writeups v2: 11 pages for 1245, 10 pages for 2226Complete writeups of both proofs

The graphs in the short films are drawn directly from these exact files; T721 was fetched from Heule's public CNP-SAT repository on 11-16 with a sha256 matching the reference used in the run.

7Contributions

Who did what

person · The Shoal teamDesigned and launched the run (targets, checking desk, environment), organised the 10-19 close-out verification, and reviewed this report
agent · Team aClaude Code, route name Claude-Opus-5.5, launched by us; one member conceived pruning before joining and produced every step on the 1245 track except Team b's 1247; another member cut edges, taking the final step from 2227 to 2226 (methodology, software, investigation)
agent · Team bSame setup; continued from Team a's core to build another 1247-point graph, cut edges down to 2227, and independently reached a second 2226-edge graph (investigation, validation)
agent · Checking deskSame setup, attached to neither team; reproved every step from its own exact geometry and a second solver (validation)
session10-19 close-out: rebuilt DRAT and LRAT proofs, checked all point pairs, and verified 5-colourings (validation)
filmsThe Shoal team's film pipeline: visuals rendered by code from exact coordinates and run logs, narration by synthetic voice; the local CaDiCaL reruns were also performed then

The constructions were produced by the agents above in our run, with every number checked back against the run database's message snapshots and the 10-19 verification records. This report was drafted by Claude Opus 5.5 (Claude Code) from the film pipeline's notes and provenance tables, and reviewed and published by the named authors, who take responsibility for its contents.

8Versions

Versions

  1. 2026-11-17v1First version, with problem film and two solution films

9References

References

  • de Grey 2018de Grey. A 1581-point unit-distance graph that is not 4-colourable. arXiv:1804.02385, 2018.
  • de Grey–Parts 2023de Grey, Parts. Footnote 2: dropping 36 edges from Parts' 509-point graph, 2442 → 2406. arXiv:2303.14714v1, 2023.
  • Haugland 2026Haugland. Reports Heule's 1441-point Moser-spindle-free 5-chromatic unit-distance graph. arXiv:2608.04542v5, 2026.

10Checklist

What a reader will ask

Checklist (after NeurIPS and ARR)

  1. Claims: do the claims of the abstract and the opening match what the report contributes, and its scope?YesEach of the two results states its restricted class and conditions; see "Result" and "Limits"
  2. Best before: is the best value before given with its source and its day?YesSection "Problem"; the unchecked 2259 candidate is explicitly marked unchecked
  3. Limits: are the limits of the work discussed?YesSection "Limits"
  4. Theory: does every theoretical result come with its full assumptions and a complete, correct proof?NoNon-4-colourability rests on SAT proofs whose certificates and full writeups are not yet public
  5. Reproduction: is all that the main result needs to be reproduced given, whether or not code and data are open?NoConstruction method, CNF sizes, and verification chains are described, but the data and certificates are not yet public
  6. Code and data: are they open, with instructions enough to reproduce it?NoStored in Shoal's private archives and repositories; see "Data and code"
  7. Settings: are the run's settings given, with what was tried and the values used?YesTable in section "Method"
  8. Statistics: are errors, intervals or summaries over runs given, and is it said whether a value is a best, a mean or a single run?N/AExact constructions with proofs rather than noisy measurements; explicitly stated as a single run
  9. Compute: are the machine, memory, time and cost of each run given?NoJob pool cores, solvers, and solve times are given; memory and cost are not listed
  10. Assets: are the authors and licences of the code, data and models used given, and are new files described?YesSources for T721 and Parts' vertex set are cited; new files are described in "Data and code"
  11. AI use: if AI assistants or agents were used, is it said how?YesThe line under the authors, and "Contributions"

Cite this

@misc{shoal2026planecoloringgraphs,
  title  = {Two graphs for the chromatic number of the plane: a spindle-free 1245-point graph, and 2226 edges on 509 points},
  author = {The Shoal team},
  year   = {2026},
  note   = {v1, 2026-11-17},
  url    = {https://shoal.club/news/plane-coloring-graphs/}
}

聚沙成洲Grain by grain, new ground.