show/hide this revision's text 2 added 1850 characters in body; edited body

Edit: Ahh, that bound's already been beaten I see! Still, I think a similar argument will give an upper bound of 24 for the chromatic number of tangent graphs of 4-spheres, and probably $\kappa_n$ rather than $\kappa_n + 1$ for the chromatic number of tangent graphs of n-spheres. Not much of an improvement, but an improvement.

More generally, though, I want to propose an approach to try to asymptotically beat the Kabatiansky-Levenshtein bound. First note that the class of graphs that can be realized as tangent graphs of unit $n$-spheres is closed under taking subgraphs. So if we can show that every such graph has a vertex of degree at most $\delta(n)$, then we can color greedily to get $\chi(G) \leq \delta(n) + 1$. This is the approach taken by Pach and Toth, for instance.

I suggest that we try to bound the average degree of a tangent graph of unit $n$-spheres. I think this may well be asymptotically smaller than the kissing number in large dimension, basically since the lattice kissing number is so much smaller than the nonlattice kissing number in general. This is more doable than bounding the minimum degree, I think, since the average degree is robust against small local changes.

Do I have any idea how to actually bound the average degree? Nothing that seems all that promising, unfortunately, although it's probably worth looking into the coding-theory analogue of the average degree. One idea I did have was to consider a "thin subpacking" which would essentially have codimension 1 -- and whose removal would disconnect the graph -- and try to induct on dimension. The problem is, unless the packing's a laminated lattice, such a "thin subpacking" doesn't really correspond to a packing in one less dimension, and I can't fix this problem in a way that gives me a reasonable bound. But maybe someone else can.

show/hide this revision's text 1

You can improve the upper bound in dimension 3 to 12.

Brooks' theorem says that a graph with maximum degree $n$ has chromatic number equal to $n+1$ if and only if the graph is a complete graph or an odd cycle. So the only graph that wouldn't be 12-colorable would be $K_{13}$. But you can easily check that there's no way to make 11 unit spheres touch two kissing spheres in dimension 3 without overlap.