Box-respecting colorings of -dimensional guillotine-partitions

A strong box-respecting coloring of an n -dimensional box-partition is a coloring of the vertices of its boxes with 2 n colors such that any box has all the colors appearing on its 2 n vertices. This is a generalization of rectangle-respecting colorings and strong polychromatic colorings to more than two dimensions. A guillotine-partition is obtained by starting with a single axis-parallel box and recursively cutting a box of the partition into two boxes by a hyperplane orthogonal to one of the n coordinate axes. We prove that there is a strong box-respecting coloring of any n -dimensional guillotine-partition. This theorem generalizes the result of Horev et al. (2009) [7] who proved the two-dimensional case. The proof gives an efficient coloring algorithm as well.