# Chromatic number of graphs of tangent closed balls

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?

• Excellent question! I've been thinking about the fact that sphere packings exhibit a "phase transition" in high dimensions, where the densest packings and highest kissing numbers tend to come from very non-rigid and even random-looking configurations. This seems like it would change the nature of the problem in high dimensions, but I don't have any evidence for this other than my gut feeling. – Harrison Brown Dec 14 '09 at 3:31
• By the way, was "disjoint spheres" or "disjoint disks" intended here? Because even in 2d the problems are different: disjoint disks give the Koebe-etc result and a tight bound of four colors, while disjoint circles (no three mutually tangent) can require five colors and it's an open problem of Ringel whether five suffice — see ics.uci.edu/~eppstein/junkyard/tangencies – David Eppstein Mar 12 '10 at 20:54
• Yes you are right, the terminology should be changed or the problem is changed. I have tried to change this here. So it should be disks I think hopefully the change fixes this. – Kristal Cantwell Mar 12 '10 at 22:30
• What's the upper bound for balls of the same size? It's sure going to be less than $13$ because you can remove a ball which touches the fewest balls, and for an outside ball this will be less than, uh, not sure. – bof May 25 '16 at 16:34

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.

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.

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.

• Is there any reason to believe that either of the Raigorodskii and Kabatiansky-Levenshtein bounds are close to best possible, though? Just a tiny improvement in either constant would solve the problem... – Harrison Brown Dec 14 '09 at 3:51
• No, I think both can be improved, but it will be quite difficult. The distance between the two bases is not just a tiny amount IMHO. Also, improving the Kabatiansky-Levenshtein bound will be a big deal. – Konrad Swanepoel Dec 14 '09 at 8:18
• D'oh! For some reason I read the constant in Raigorodskii's bound as 1.293 instead of 1.239. (Apparently I'm temporarily dyslexic when I'm looking at this page.) That's where the hope that someone could push the base just a bit higher came from, but 0.09 is a lot bigger than 0.03. – Harrison Brown Dec 14 '09 at 16:56
• I think I misunderstand something: the bounds of Raigorodskii and Kabatiansky-Levenshtein are for different problems! It is like comparing apples and alligators! – Boris Bukh Dec 17 '09 at 12:17
• @Boris: One of the questions that Kristal asks above (in the last paragraph), is whether it can be shown if the maximum chromatic number of tangency graphs of a packing of balls in dimension n (alligator) is different from the chromatic number of the n-dimensional unit distance graph (apple). My answer was just an attempt to explain what I know about both numbers, and that I think it would be difficult to find out if alligators are smaller than apples ;-) – Konrad Swanepoel Dec 17 '09 at 14:26

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.

• It is possible for 12 slightly larger spheres to touch a smallest one. But you're right, then one of them would have to be more to the left. G. Kertesz (Nine points on the hemisphere. Colloq. Math. Soc. J. Bolyai (Intuitive Geometry, Szeged 1991) 63 (1994), 189–196) showed that at most 8 unit spheres can touch an open hemisphere of a unit sphere, so in fact you have minimum degree 8. – Konrad Swanepoel Mar 12 '10 at 18:14
• I don't understand the first sentence in the second paragraph. What if the smallest is not extreme? If you are talking about unit spheres, then order the sphere by height and you get one-side kissing number plus one as upper bound. If you allow the spheres to have different radii, then order the spheres by size and you get the kissing number plus one as the upper bound. How can you order them by two criterions at the same time? – Hao Chen Feb 7 '15 at 14:57
• A clarification: Choose the sphere $S$ to be smallest, and subject to that choose it to be extreme. I claim without proof that if a sphere kisses 12 others of equal or greater radius, then all 13 spheres have equal radius. Furthermore the sphere kissed by 12 others has its centre in the convex hull of the other 12 centres, and therefore is not extreme (of these 13 spheres) in any direction. – Andrew D. King Feb 12 '15 at 17:58
• Your 'claim without proof' is false: take 12 spheres positioned at the vertices of a regular icosahedron, with diameters equal to the edge length of the icosahedron. Then the sphere centred on the origin which is (externally) tangent to those twelve spheres has radius slightly smaller than the others. Historically, this is why some people, such as David Gregory, conjectured that the kissing number might be 13 rather than 12. (Newton got it correct, though.) – Adam P. Goucher Mar 29 '19 at 15:19

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.
• Guys, I don't understand it. I just posted a better lower bound in another answer mathoverflow.net/a/195846/20595, then this answer got two votes ... what is happening? – Hao Chen Feb 6 '15 at 22:12
• When you bump a question, all answers get more attention. – Douglas Zare Feb 11 '15 at 11:05

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.

• Aubrey de Grey's graph shows that (in two dimensions) the chromatic number of unit distance graphs is strictly larger than the chromatic number of graphs of tangent balls. (But of course that wasn't known when you wrote the answer!) – Adam P. Goucher Mar 29 '19 at 15:21

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.

• Graphs of tangent unit disks in the plane are called "penny graphs". Finding an example requiring four colors such as you do above is exercise 8.4.7 of <i>Pearls in Graph Theory</i>, Hartsfield and Ringel, Dover 2003, p.177. – David Eppstein Dec 13 '09 at 19:53

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.

• Either I or Cibulka misunderstand the lemma of Erdös and Sös. The graph in your first paragraph is a Johnson graph J(n,3), it's chromatic number is at most $n$ (Graham and Sloane, 1980). I then checked the paper of Larman and Rogers, it seems that Equation 2.1 in Cibulka's thesis should be about the clique number, not the independence number. Would you please confirm these things? – Hao Chen Jan 10 '14 at 21:05
• FYI, in the paper of Larman and Rogers, the lemma goes like this: "if more than n' (n'=n, n+1, n-1 as you said) triples are chosen from n objects, at least one pair of triples have EXACTLY one element in common" – Hao Chen Jan 10 '14 at 21:23
• I was able to recheck the problem one year later. It's actually not a mistake of Cibulka. His "2-distance graph" is not hamming distance, but Euclidean distance. So two vertices are connected if they differ in 4 (not 2) coordinates (i.e. share exactly one coordinate). This is the same setting of Larman and Rogers. However, the graph you discribe in the first paragraph is a $\sqrt{2}$-graph, so you can not use the lemma of Erd\"os and S\'os. – Hao Chen Oct 20 '14 at 11:56
• I think your objection about the lemma I used is right and I cant fix it so I have removed the first two paragraphs which had this result. – Kristal Cantwell Feb 6 '15 at 22:35
• @cantwell, thank you for response. Your halved-cube example is wonderful, and was one of the motivation behind this answer. Actually, his problem can be regarded as the "opposite" of the Borsuk conjecture, which is very interesting. – Hao Chen Feb 6 '15 at 22:43

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.

• What do you mean by a tangent graph of unit n-spheres? Is this in a packing of unit spheres, or in any collection of (possibly intersecting) unit spheres, which would be equivalent to the unit distance graph in Kristal's question? In the non-overlapping case, by considering the average degree, you are essentially counting (double) the number of occurrences of the minimum distance in a set of n points. Here the average degree is bounded above by the kissing number and from below essentially by the lattice kissing number. In the overlapping case (unit distance graph) there is no bound... – Konrad Swanepoel Dec 14 '09 at 16:22
• ... on the average degree, because of the Lenz construction. – Konrad Swanepoel Dec 14 '09 at 16:23
• @Konrad: Packing of unit spheres -- I was aiming for "graph of tangent spheres" but got confused. So a lot of the post is wildly speculative, but basically I conjecture that the average degree in a graph of tangent spheres grows as the lattice kissing number rather than the kissing number. In high dimensions the lattice kissing number should grow relatively slowly, although I don't have an actual upper bound. (Does someone else?) – Harrison Brown Dec 14 '09 at 16:38
• For four dimensions the graph has a minimum number of tangent spheres of 24 at a minimial sphere but elsewhere their could be 25 more spheres tangent to a sphere because not are all the same size. So I don't see how I can get the number below 25. Also it is not clear that the closest packing is always a lattice in 10 dimensions there are irregular packings which have greater density see en.wikipedia.org/wiki/Sphere_packing. – Kristal Cantwell Dec 15 '09 at 2:18
• @Kristal: My post is entirely about the case where all the spheres have radius 1. I agree that Brooks' theorem doesn't help if the spheres are different sizes. And yes, the irregularity of good packings in high dimension is what I want to try to take advantage of! If it's true that the average kissing number of the spheres in any packing grows at a rate comparable to the lattice kissing number rather than irregular packings, and that seems plausible, we could get bounds resembling the lattice number, which would be nice. – Harrison Brown Dec 15 '09 at 2:39

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.

• Once again, by Brooks' theorem, we can improve that to 18 if we can show that $K_18$ can't be represented as a graph of tangent unit 4-spheres! :) (Can we show that, by the way? I haven't done the math, but the volume argument seems like it might fail. But that's a pretty weak analysis, so presumably something better will work.) – Harrison Brown Dec 16 '09 at 21:57
• @Harrison: You can have at most n+1 pairwise tangent unit spheres in dimension n. If you take one of the centers at the origin, then it is not difficult to show that the other centers are linearly independent. – Konrad Swanepoel Dec 16 '09 at 22:06
• That's... Huh. Wow, yeah, I can't believe I didn't think of that. Essentially the same proof but more geometrically stated: the abstract simplicial complex corresponding to an m-simplex isn't a (geometric) simplicial complex if you embed it in n-space, for n < m-1. Which I knew, but totally didn't think about. So the chromatic number is at most 18. – Harrison Brown Dec 16 '09 at 22:45
• There are hyperspheres with more than 18 tangent spheres in this graph The minimum number of tangencies is 18 at two sphere so that limits the chromatic number to 19. I think Brooks theorem applies in this case only to graphs with an a maximum number of adjacent points at 18 for all points. There are only two special points which have this property of having the one-sided kissing number 18 others could have as many as 24 hyperspheres adjacent. – Kristal Cantwell Dec 16 '09 at 23:33
• @Kristal: You're right, of course; I misunderstood the argument, and somehow my sanity check failed. (I know that the kissing number in dimension 4 is 24!) – Harrison Brown Dec 17 '09 at 1:47

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.