WorksMathematics
A Lower Bound for the Chromatic Number of Ball-Packing Graphs
Abstract
For every odd prime power , we construct a finite packing of congruent balls in dimension whose contact graph requires at least 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 graphs and uses their Taylor extensions. We give an explicit finite-field adjacency rule for the -vertex graph , prove its strong regularity, determine its spectrum and projection matrix, establish , and construct a two-distance embedding in . Its Taylor extension has vertices. We prove its distance-regularity, compute its intersection array, construct a three-distance embedding in , and prove . The chromatic lower bound follows by realizing 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 uses the Schläfli and Gosset graphs and gives a packing of 56 congruent balls in requiring at least 14 colors.