Skip to main content
4 of 7
added 1158 characters in body
Hao Chen
  • 2.6k
  • 19
  • 29

The coloring of higher dimensional ball packings.

A ball packing is a collection of balls with disjoint interiors. The tangency graph of a ball packing takes the balls as vertices and connect two vertices if and only if they are tangent. Planar graphs are the tangency graphs of 2-dimensional disk packings. So the following is a generalization of four-color theorem.

Question: what is the maximum chromatic number $\chi_d$ for the tangency graph of a ball packing in dimension $d$?

I believe that everyone can prove that $\chi_d\le\kappa_d+1$ where $\kappa_d$ is the kissing number. The question was asked by Bagchi and Datta (2012) who gave the trivial lower bound $\chi_d\ge d+2$.

As far as I know, Maehara (2007) first attack the problem for dimension $3$. His construction for lower bound uses Moser spindle. It generalizes to higher dimensions and gives $\chi_d\ge d+3$.

The problem has also been asked on MO. The only new result appears in an answer of Cantwell. He proposed two constructions: One uses binary code and gives quadratic lower bound, but I think he made some mistakes. The other uses halved cubes. It can be generalized to higher dimensions by a result of Liniail, Mishulam and Tarsi (1988) and gives $\chi_d\ge d+4$ for infinitely many $d$.

So the current status is: $d+4\le\chi_d\le\kappa_d+1$. There is a large gap in between.

Hao Chen
  • 2.6k
  • 19
  • 29