PreprintarXiv licencearXiv
Small 5-chromatic unit-distance graphs in disks of radius 3/2, 5/4 and 23/20
Abstract
We give three explicit unit-distance graphs in the plane with chromatic number 5 whose vertices lie in small disks: a graph with 773 vertices inside an open disk of radius 3/2, one with 5713 vertices inside an open disk of radius 5/4, and one with 8168 vertices inside an open disk of radius 23/20. The smallest examples previously reported for these radii have 11725, 11725 and 31171 vertices. All coordinates are exact elements of Q(sqrt3, sqrt5, sqrt11). In each case 5-chromaticity is certified by an explicit 5-colouring and a DRAT proof that no 4-colouring exists. The 773-vertex graph is vertex-critical.
Related
- On the k-Distance Chromatic Number of Unicyclic Graphs
- Independence number, essential connectivity and the distance spectral radius of graphs
- Some results on the distance spectral radius and edge-disjoint spanning trees of graphs
- Bounded chromatic number of graphs with small clique number and large minimum degree
- On the classification of $2$-distance-primitive graphs of small valency
BibTeX
@misc{shukla2026small,
title = {{Small 5-chromatic unit-distance graphs in disks of radius 3/2, 5/4 and 23/20}},
author = {Chandan Shukla},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06269},
eprint = {2611.06269},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06269},
}
RIS
TY - UNPB
TI - Small 5-chromatic unit-distance graphs in disks of radius 3/2, 5/4 and 23/20
AU - Chandan Shukla
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06269
UR - https://arxiv.org/abs/2611.06269
AB - We give three explicit unit-distance graphs in the plane with chromatic number 5 whose vertices lie in small disks: a graph with 773 vertices inside an open disk of radius 3/2, one with 5713 vertices inside an open disk of radius 5/4, and one with 8168 vertices inside an open disk of radius 23/20. The smallest examples previously reported for these radii have 11725, 11725 and 31171 vertices. All coordinates are exact elements of Q(sqrt3, sqrt5, sqrt11). In each case 5-chromaticity is certified by an explicit 5-colouring and a DRAT proof that no 4-colouring exists. The 773-vertex graph is vertex-critical.
ER -