e5 <= 2243: 5-chromatic unit-distance graphs in the plane with few edges
收藏资源简介:
A 509-vertex unit-distance graph in the Euclidean plane with chromatic number 5 and 2243 edges, 163 edges below the published bound of e5 <= 2406 (de Grey and Parts, Geombinatorics 32(2), 2022) and 16 below the 2259-edge graph of md-amer (2026). Obtained by repeated plateau moves: add back an edge previously deleted from Parts's 509-vertex graph, delete a different edge to reach an equal-sized but structurally different graph, then descend. Edge-criticality and being an UNSAT-core fixpoint do not imply edge-minimality. Every graph in the chain is verified by exact unit distances in Q(sqrt3, sqrt5, sqrt11) using integer arithmetic with no floating point, an unpinned or validly pinned UNSAT for chi >= 5, an explicit 5-colouring, and a DRAT refutation checked by drat-trim.



