Take the 2-minute tour ×


Graphs of Tangent Spheres






share|improve this question
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

11 Answers 11

up vote 7 down vote accepted

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.


share|improve this answer

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 (Lov\'asz number) 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.

share|improve this answer







share|improve this answer

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.

share|improve this answer
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 at 22:12
When you bump a question, all answers get more attention. –  Douglas Zare Feb 11 at 11:05



share|improve this answer



share|improve this answer
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 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 at 17:58




There is more about this here

share|improve this answer




share|improve this answer
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 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 at 22:43

You can improve the upper bound in dimension 3 to 12.






share|improve this answer
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


share|improve this answer




share|improve this answer

Your Answer


