Return to Answer

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. One result is an answer of Cantwell. It 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.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.

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. One result is an answer of Cantwell. It 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.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.

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.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.

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. One result is an answer of Cantwell. It 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.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.

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.

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.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power. There are many other ball packings with high chromatic number, see this answer. The gap is still very large.