The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What happens when disks are replaced by closed balls? By closed balls of higher dimension? I have already asked one question about this here:
The question I want to ask here is what is known about the chromatic numbers of these graphs? I have updated the numbers and changed the arguments in the following based on some of the answers.
Assume the chromatic number is 14 or more and we have the smallest such graph that is colorable with 14 or more colors. Take one of the smallest closed balls then since the kissing number for three dimensions is 12 there are at most 12 closed balls tangent to this closed ball. Remove this closed ball then the remaining graph can be colored in 13 or less colors. Color it with 13 colors. Then add the closed ball back in since it is tangent to only 12 closed balls it can be given one of the thirteen colors so we have the entire graph can be colored with thirteen colors which gives a contradiction so the chromatic number must be 13 or less. We have an lower bound of 6 from a spindle constructed according to David Eppstein's answer. Can we improve on the 6 to 13 range?
We have the lower bound is a quadratic function and we have an upper bound that is exponential. Which of these two is right?
Is there a case where closed balls of different sizes raise the chromatic number from closed balls the same size?
Finally based on the existing chromatic numbers I am wondering if it is possible to answer this question. Is there a dimension where the chromatic number of the unit distance graph is different from the chromatic number of the graphs in that dimension of tangent closed balls. The unit distance graph is the set of all points in the $n$-dimensional space with two points connected if their distance is one. For dimension two the chromatic number is known to be in the range from 4 to 7. For dimension three the range is 6 to 15. For the graphs of tangent disks we have a chromatic number of 4 and for closed balls a range from 6 to 13. So the possibility that the chromatic numbers of the two types of graphs are the same has not yet been eliminated. So the specific question is what is known and what can be proved about the chromatic number of the graphs of tangent closed balls?
Best Answer
It's easy to form sets of five mutually-tangent spheres (say, three equal spheres with centers on an equilateral triangle, and two more spheres with their centers on the line perpendicular to the triangle through its centroid). Based on this, I think it should be possible to construct a set of spheres analogous to the Moser spindle [http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem] that requires six colors: spheres a, b, and c, where a and b have four mutual neighbors that are all adjacent to each other, a and c have another four mutual neighbors that are all adjacent to each other, neither a and b nor a and c are adjacent, but b and c are adjacent.
I have no idea how tight this lower bound might be, but it's at least better than four.