files / problems / hadwiger-nelson-plane / compute / q1 / README.md

2.2 KB · on GitHub

q1 — exact Parts spawns

This campaign starts from Parts' published 509-vertex graph and builds two finite exact-coordinate supergraphs.

The search asks whether either supergraph is 5-colorable. A stored coloring kills not only the full graph but every subgraph formed by deleting added vertices. Coordinates are in parts509.vtx, sourced from the Polymath data archive via the Lean formalization repository; udg.py rebuilds every unit edge in Q(3,5,11)\mathbb Q(\sqrt3,\sqrt5,\sqrt{11}).

Search setup:

python3 -m venv .venv
.venv/bin/pip install python-sat
./run_search.sh

Certificate replay does not require PySAT:

./run_all.sh

The Python verifier reconstructs every exact edge from coordinates and checks the stored colors. The C verifier independently checks the edge-list/coloring certificate. A SAT result is a killed finite candidate, not a lower bound.

Result

Both candidates are five-colorable.

graph vertices unit edges SAT time color-class sizes
G∪ρGG\cup\rho G 933 4,651 0.015 s 211, 203, 203, 165, 151
GG plus all 677 reserve points 1,186 7,440 2.89 s 259, 251, 225, 220, 231

Times are from Python 3.13.5, python-sat 1.9.dev15, and its CaDiCaL 1.9.5 binding. They are only a search log; the committed colorings are the certificates. Since the second coloring restricts to every subgraph obtained by deleting reserve points, it excludes all 26772^{677} add-only subsets as six-chromatic witnesses. This says nothing about deleting base vertices, introducing other coordinates, or composing different layers.