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).

## Return to Answer

2 addition of material

One of the questions I asked above was if the addition of different size spheres changes maximum chromatic number. I can prove it does not for dimension equals 2. We have the set of graphs of tagent tangent circles is the same as the set of planar graphs. Now the maximum chromatic number of a planar graph is 4 by the four color theorem. What is needed is a graph of circles of the same radius which has chromatic number four. Assume that every such graph can be colored with three colors Now look any four circles of unit radius $a$, $b$, $c$ and $d$ with $a$, $b$ and $c$ mutually tangent and $b$, $c$ and mutually tangent. The only way this can happen is if $a$, $b$ and $c$ have their centers forming an equilateral triangle of side 2 as do $b$, $c$ and $d$. If there is a three coloring we have $a$ and $d$ forced to be the same color. We can arrange a series of these graphs in a cycle such that $a$, $d$,... $x$ have the same color and $x$ is tangent to $a$. This will give a contradiction. So this graph has chromatic number four and we are done.

So the next case to look at is dimension 3. By an argument similar to above the chromatic number of graphs of tangent unit spheres is at least 5 and we have the chromatic number for these graphs is 9 or less by "On the independence number of coin graphs" by János Pach and Géza Tóth, in Geombinatorics, vol. 6, num. 1, 1996, p. 30-33. So we have the range 5 to 9 for maximal chromatic number of graphs of tangent three dimensional spheres of unit radius as opposed to the range 6 to 12 for maximal chromatic number of graphs of tangent three dimensional spheres.

1

One of the questions I asked above was if the addition of different size spheres changes maximum chromatic number. I can prove it does not for dimension equals 2. We have the set of graphs of tagent circles is the same as the set of planar graphs. Now the maximum chromatic number of a planar graph is 4 by the four color theorem. What is needed is a graph of circles of the same radius which has chromatic number four. Assume that every such graph can be colored with three colors Now look any four circles of unit radius $a$, $b$, $c$ and $d$ with $a$, $b$ and $c$ mutually tangent and $b$, $c$ and mutually tangent. The only way this can happen is if $a$, $b$ and $c$ have their centers forming an equilateral triangle of side 2 as do $b$, $c$ and $d$. If there is a three coloring we have $a$ and $d$ forced to be the same color. We can arrange a series of these graphs in a cycle such that $a$, $d$,... $x$ have the same color and $x$ is tangent to $a$. This will give a contradiction. So this graph has chromatic number four and we are done.