MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 terminology correction

# Chromatic number of graphs of tangent spheresclosedballs

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 circle disk packing whose graph is $G$. What happens when circles disks are replaced by spheresclosed balls? By spheres closed balls of higher dimension? I have already asked one question about this here:

http://mathoverflow.net/questions/8031/graphs-of-tangent-spheres

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 spheres closed balls then since the kissing number for three dimensions is 12 there are at most 12 spheres closed balls tangent to this sphereclosed ball. Remove this sphere closed ball then the remaining graph can be colored in 13 or less colors. Color it with 13 colors. Then add the sphere closed ball back in since it is tangent to only 12 spheres 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 spheres closed balls of different sizes raise the chromatic number from spheres 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 spheresclosed 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 circles disks we have a chromatic number of 4 and for spheres 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 spheresclosed balls?

4 revision

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 circle packing whose graph is $G$. What happens when circles are replaced by spheres? By spheres of higher dimension? I have already asked one question about this here:

http://mathoverflow.net/questions/8031/graphs-of-tangent-spheres

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 spheres then since the kissing number for three dimensions is 12 there are at most 12 spheres tangent to this sphere. Remove this sphere then the remaining graph can be colored in 13 or less colors. Color it with 13 colors. Then add the sphere back in since it is tangent to only 12 spheres 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 5 6 from spheres at the points of a tetrahedron together with the central point or the Moser spindle constructed according to David Eppstein's answer. Can we improve on the 5 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 spheres of different sizes raise the chromatic number from spheres 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 spheres. 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 circles we have a chromatic number of 4 and for spheres a range from 5 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 spheres?

3 minor change

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 circle packing whose graph is $G$. What happens when circles are replaced by spheres? By spheres of higher dimension? I have already asked one question about this here:

http://mathoverflow.net/questions/8031/graphs-of-tangent-spheres

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 spheres then since the kissing number for three dimensions is 12 there are at most 12 spheres tangent to this sphere. Remove this sphere then the remaining graph can be colored in 13 or less colors. Color it with 13 colors. Then add the sphere back in since it is tangent to only 12 spheres 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 5 from spheres at the points of a tetrahedron together with the central point or the Moser spindle. Can we improve on the 5 to 13 range?

As we increase the dimensions of the tangent spheres the chromatic number goes to infinity just take d+1 tangent spheres we can improve

We have the lower bound to is a quadratic function and we get have an upper bound that is exponential. Which of these two is right? Can we get a subexponential upper bound?

Is there a case where spheres of different sizes raise the chromatic number from spheres 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 spheres. The unit distance graph is the set of all points in the n-dimensional $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 circles we have a chromatic number of 4 and for spheres a range from 5 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 spheres?

2 revision
1