betaFeedback

WorksMathematics

A Lower Bound for the Chromatic Number of Ball-Packing Graphs

Abstract

For every odd prime power qq, we construct a finite packing of congruent balls in dimension d=q2−q+1d=q^2-q+1 whose contact graph requires at least 2d2d 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 C20C_{20} graphs and uses their Taylor extensions. We give an explicit finite-field adjacency rule for the q3q^3-vertex graph HqH_q, prove its strong regularity, determine its spectrum and projection matrix, establish α(Hq)=qα(H_q)=q, and construct a two-distance embedding in Rq(q−1)\R^{q(q-1)}. Its Taylor extension TqT_q has 2(q3+1)2(q^3+1) vertices. We prove its distance-regularity, compute its intersection array, construct a three-distance embedding in Rd\R^{d}, and prove α(Tq)=q+1α(T_q)=q+1. The chromatic lower bound follows by realizing TqT_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=3q=3 uses the Schläfli and Gosset graphs and gives a packing of 56 congruent balls in R7\R^7 requiring at least 14 colors.

Paper details

vlnc:W_zz4wushr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…