Cuboid representable graphs (2011)

Originators:  Mu-Tsun Tsai  (presented by Mu-Tsun Tsai - REGS 2011)

Definitions: A cuboid in Euclidean space is a cartesian product of intervals in each coordinate. A cuboid representation of a graph G (in 3 dimensions) maps each vertex of G to a cuboid with its vertices at integer lattice points, such that distinct vertices of G map to cuboids that have no common region of positive volume, and such that uvE(G) if and only if the intersection of the corresponding cuboids has positive area. A bar representation of a graph is a cuboid representation such that all each cuboid projects to an interval of length 1 in at least two of the three dimensions. Higher dimensional analogues are defined similarly. When such representations exist, we say that G is cuboid-representable or bar-representable.

Background: One way to generalize the map coloring problem to space is to consider coloring regions in 3-dimensional space so that adjacent regions (those whose boundaries intersect with positive area) receive different colors. If no restriction is applied to the regions, then the arbitrarily many colors may be needed. Restricting the regions to cuboids or straight bars may bound the number of colors.

Conjecture 1: The chromatic number of a cuboid-representable graph is bounded by a constant, and the same is true for the higher-dimensional analogue.

Problem 2: Characterize the family of cuboid-representable or bar-representable graphs.

Question 3: It follows easily from the Four Color Theorem that the chromatic number of a bar-representable graph is at most 16. Is there a better bound?

Comment: Degeneracy of these graphs is not bounded, since it is easy to represent all complete bipartite graphs.