遇见数据集

A Moser-spindle-free 5-chromatic unit-distance graph on 557 vertices in the plane

收藏
Zenodo2026-10-31 更新2026-11-05 收录
官方服务:

资源简介:

A unit-distance graph in the Euclidean plane with 557 vertices and 2811 edges, chromatic number exactly 5, containing no Moser spindle as a subgraph. Coordinates are exact elements of Q(zeta_21): each point is (sum over k of a_k zeta_21^k)/7 with the integer coefficient vectors a given in graph557.json. Float coordinates are included for convenience only; all verification is exact. A Moser spindle would need sqrt(-11), which is not in Q(zeta_21). Prior work and credit: J. K. Haugland gave an explicit spindle-free 5-chromatic example on 2131 vertices (arXiv:2608.04542), and the smallest published spindle-free example has 1441 vertices. Sergi Galan made available online an 852-vertex spindle-free 5-chromatic graph (https://github.com/decalion89/chromatic-number-of-the-plane, data/flat852, September 2026). The 126 unit directions used here are the same as in Galan's construction (from Haugland's heptagon lattice); our configuration (2967 vertices) was built and reduced independently to 557 vertices by SAT-based vertex elimination (kissat; single and batched removals, combination of independent branches). Both graphs live in the same lattice, so many points coincide. (The credit line in the included README.txt, which calls the graph a reduction of Galan's graph, is incorrect and superseded by this paragraph.) Files: graph557.json (exact and float coordinates, edge list, proper 5-colouring), verify.py (exact verifier: every listed edge has squared length exactly 1, no other pair does, no Moser spindle subgraph, included 5-colouring is proper), four_plain.cnf and four_symbreak.cnf (the 4-colouring formulas; both unsatisfiable, so the chromatic number is exactly 5), README.txt (usage and checksums). four_symbreak.cnf was proved unsatisfiable by kissat with a DRAT proof checked by drat-trim (s VERIFIED); the proof can be regenerated with kissat. The DRAT proof itself (6.1 GB; xz-compressed in two parts, with SHA-256 checksums) is attached to the GitHub release https://github.com/chandanshukla1989/moser-free-557/releases/tag/v557 .

提供机构:
Zenodo
创建时间:
2026-10-31
二维码
社区交流群
二维码
科研交流群
商业服务