A Lower Bound for the Chromatic Number of Ball-Packing Graphs
For every odd prime power $q$, we construct a finite packing of congruent balls in dimension $d=q^2-q+1$ whose contact graph requires at least $2d$ colors. Consequently, the ball-packing chromatic number satisfies $\chiball(q^2-q+1)\ge2(q^2-q+1)$, and the same lower bound holds for congruent-ball packings. The construction starts from the complements of Hubaut's $C_{20}$ graphs and uses their Taylor extensions. We give an explicit finite-field adjacency rule for the $q^3$-vertex graph $H_q$, prove its strong regularity, determine its spectrum and projection matrix, establish $α(H_q)=q$, and construct a two-distance embedding in $\R^{q(q-1)}$. Its Taylor extension $T_q$ has $2(q^3+1)$ vertices. We prove its distance-regularity, compute its intersection array, construct a three-distance embedding in $\R^{d}$, and prove $α(T_q)=q+1$. The chromatic lower bound follows by realizing $T_q$ as the contact graph of equal-radius balls and bounding the size of every color class. All coordinates, distances, and independence bounds are derived explicitly. The case $q=3$ uses the Schläfli and Gosset graphs and gives a packing of 56 congruent balls in $\R^7$ requiring at least 14 colors.
Authors
- Dan Ismailescu (ORCID: https://orcid.org/0000-0002-5566-5080)
- Sunwoo Lee
- Terry Lee
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.23767
- Primary Topic
- Finite Group Theory Research
- Type
- preprint