Chromatic number of graphs of tangent closed balls

Question

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:

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 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?

Answer 1

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.

Answer 2

Update May 2016

I removed the updates in Oct 2015. I was trying to combine two copies of strongly regular ball packings to double the chromatic number. But it has been point out that my construction was buggy.

Previous examples obtained in January 2015

Inspired by Bodarenko's counter-example to the Borsuk conjecture, I recently find many ball packings whose chromatic number is significantly higher than the dimension. There tangency graphs are all strongly regular. A note is available on arXiv and here (up to date).

Here I list their parameters, dimensions and lower bounds (Hoffman) for the chromatic numbers. Many of these parameters are for the complement to the more famous graph, e.g. Higman-Sims graph.

• $(100, 77, 60, 56)$ (Higman-Sims graph), dimension 22, $\chi\ge 80/3$.
• $(105, 72, 51, 45)$, dimension 20, $\chi\ge 25$.
• $(120, 77, 52, 44)$, dimension 20, $\chi\ge 80/3$.
• $(126, 75, 48, 39)$, dimension 20, $\chi\ge 26$.
• $(162, 105, 72, 60)$ (Local McLaughlin), dimension 21, $\chi\ge 36$.
• $(175, 102, 65, 51)$, dimension 21, $\chi\ge 35$.
• $(176, 105, 68, 54)$, dimension 21, $\chi\ge 36$.
• $(176, 85, 48, 34)$, dimension 22, $\chi\ge 88/3$.
• $(243, 132, 81, 60)$ (Delsarte graph), dimension 22 $\chi\ge 45$.
• $(253, 140, 87, 65)$, dimension 22, $\chi\ge 143/3$.
• $(275, 162, 105, 81)$ (McLaughlin graph), dimension 22, $\chi\ge 55$.
• $(276, 135, 78, 54)$, dimension 23, $\chi\ge 46$.
• $(729, 520, 379, 350)$, dimension 112, $\chi\ge 621/5$.

Furthermore, there are two infinite families with high chromatic number (here $q$ is a prime power).

• $(q^3, (q+1)(q^2-1)/2, (q+3)(q^2-3)/4+1, (q+1)(q^2-1)/4)$ (complements to Hubaut's C20), dimension $q^2-q$, $\chi\ge q^2$.
• $((q^3+1)(q+1), q^4, (q^2+1)(q-1)q, q^3(q-1))$ (complement to the point graph of the generalized quadrangle $(q,q^2)$), dimension $q^3-q^2+q$, $\chi=q^3+1$.

Note that the last case is an equality. This is the first non-constant lower bound for $\chi-d$.

Hope this helps future improvement.

Answer 3

I would guess that the unit distance graph has a higher chromatic number than the tangency graph of a sphere packing in high dimensions, but this is surely an open question. Here are some known results:

The best known lower bound for the chromatic number of the unit distance graph of Euclidean n-space is by Raigorodskii (Electronic Notes in Discrete Mathematics 28 (2007) 273–280): $1.239\dots^n$.

On the other hand, the best upper bound for the chromatic number of the tangency graph of a packing of spheres in dimension n that I can think of is the following simple-minded one:

Let $\kappa_n$ denote the kissing number in n-dimensional Euclidean space. This is the maximum number of non-overlapping unit spheres that can touch some fixed unit sphere.

Then the chromatic number of the tangency graph of a sphere packing is at most $1+\kappa_n$. This is seen using a greedy colouring as follows: take a sphere of smallest radius. Since all spheres touching it have radius at least as large, their number is bounded above by $\kappa_n$. So we can colour this sphere and remove it from the graph. Repeat until the graph is empty.

By the Kabatiansky-Levenshtein bound (Problems of Information Transmission 14 (1978) 1–17), $\kappa_n\leq 1.32042\dots^{n}$. This is some distance away from the unit distance lower bound, and I guess it won't be easy to decide whether the unit distance chromatic number is really larger when the dimension is large.

Answer 4

Certainly 12 is an upper bound for dimension 3 with not necessarily equal radii. To see this, it suffices to show that any such graph has minimum degree at most 11.

Take a smallest sphere whose centre is extreme in some dimension (e.g. leftmost). This sphere cannot touch 12 other spheres, because if it did, all these spheres would have to be smallest as well, and one would be further left, contradicting our choice.

Answer 5

I find a paper of Hiroshi Maehara (http://link.springer.com/article/10.1007%2Fs00373-007-0702-7). He studies packing of a) closed balls, b) balls on a table, c) unit balls, d) unit balls within a restricted height.

• For packing of closed balls, the chromatic number he obtained is between 6 and 13, as expected by many here.
• For packing of balls on a table, the chromatic number is between 5 and 6;
• For packing of unit balls, the chromatic number is between 5 and 10.
• For packing of unit balls within height $0$ and $2+\sqrt2$, the chromatic number is between 4 and 6.
• For packing of unit balls with restricted height, the cromatic number is at least 4 or 5 depending on the restriction.

Answer 6

One of the questions I asked was if there was a difference between the chromatic number of the unit distance graph and the graphs of tangent spheres. In dimension 2 there is an answer to this under a certain choice of axioms under the axiom system ZF+DC+LM. In that case the chromatic number of the plane is five or greater. Then the chromatic number of the unit distance graph will be bigger than either the maximum chromatic number graphs of tangent circles or the maximum chromatic number of graphs of unit spheres which are both 4. The axiom system makes all sets measurable that is LM, the DC is dependent choice which is weaker than the axiom of choice. This result is from the following paper:

Axiom of choice and chromatic number of the plane Journal of Combinatorial Theory Series A Volume 103 , Issue 2 (August 2003) Pages: 387 - 391

I think it is also discussed in The Mathematical Coloring Book by Alexander Soifer.

There is more about this here.

Answer 7

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

Answer 8

For $n$ we can get $n+2$ either by using the Moser spindle as noted in another answer or simply by taking a simplex which has $n+1$ spheres each tangent to each other and then inserting a smaller sphere whose center is the center of the simplex and which is tangent to the other spheres this set of $n+2$ spheres tangent to each other needs $n+2$ colors so we have the chromatic number is $n+2$ or more.

For dimension 5 we can take all points whose coordinates are one and zero and which have an even number of 1's. There are 16 such points. If two points are different at least two coordinates are different. Suppose we have an 7 coloring of these points with all coordinates differing by 2. Then three of them must have the same color. Then no two points with four ones can have the same color or they would differ by two coordinates. The point with all zeros must have different color than any point with two ones or they would differ by two coordinates. No three points with two ones can have the same color or two would share the same coordinate value and they would differ by two coordinates. So These points must be colored with eight different colors two avoid two the same color differing by two coordinates.

So if we look at the spheres of radius $\sqrt2$ centered about the points with zeros and ones as coordinates with an even number of ones. They form a graph of tangent spheres in five dimensional space with chromatic number 8. We can take a sphere centered at the point whose coordinates are all 1/2 and choose a radius to get it tangent to all the spheres in the graph this graph will have chromatic number 9. So we have the chromatic number of 5 dimensional space is 9 or more. Here again this is realizable only because $\sqrt2$ is the minimum distance between these points a lot of similar constructions that work for the chromatic number of a space don't work because they use a distance other than the minimum.

Answer 9

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.

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.

Answer 10

I can show that the maximum chromatic number of a graph of tangent unit hyperspheres in four dimensions is 19 or less. Take the two hyperspheres in the graph at whose centers have maximum distance $d$. This line between the centers will intersect each hypersphere twice two of these points of interesection will be between the two centers and the other two will contain the other four points between them. One these latter two points construct hyperplanes perpendicular to the line. If any hypersphere cuts the hyperplane associated with one of these two hyperspheres or lies on the other side of this hyperplane then the distance between its center and the other hypersphere will be greater than $d$ so any hypersphere that is tangent to one of these hypersphere is will lie on the halfspace determined by the hyperplane that contains the hypersphere. That means we with regards to this hyperspere and hyperplane the definition of one-sided kissing number is satisfied. We have the one-sided kissing number of four dimensional space is 18. See this paper. So this sphere can have at most 18 tangent hyperspheres. Then its chromatic number will be at most 19.

Answer 11

Wondering why Andrew D King's answer (or Konrad Swanepoel's comment on it) was not upvoted. (As a newbie, I cannot, nor can I comment.) If we cheekily let $\hat{\kappa}_n$ denote the hemispherical kissing number in $n$-dimensional space, defined here to mean the maximum number of mutually disjoint $n$-dimensional unit hyperspheres tangentially adjacent to a $n$-dimensional unit hemihypersphere, then the corresponding chromatic number is at most $\hat{\kappa}_n+1$ (by Andrew's argument). Konrad mentioned that $\hat{\kappa}_3\le8$, giving an upper bound of $9$ for colouring sphere packings. For larger $n$, certainly the base in the Kabatiansky-Levenshtein bound on $\kappa_n$ can be beaten for $\hat{\kappa}_n$!

Edit: My original post would have implied a nice short proof of the $5$-colour theorem, but alas there are easy counterexamples to the claim that the maximum minimum degree (a.k.a. degeneracy) is at most $\hat{\kappa}_n$.

However, $\kappa_n$ is an upper bound for colouring $n$-dimensional hypersphere packings using Andrew's argument.