Coloring blocks in 3-space
by
Daniel M. Martin
Emory University
Coauthors: Colton Magnant

A block is the cartesian product of three closed finite nontrivial intervals of the real line. If B is a block, we denote its component intervals by X_B, Y_B, and Z_B, so that B = X_B ×Y_B ×Z_B.

A set of blocks is said to be a valid configuration if no two blocks in the set share an interior point. They are, however, allowed to share boundary points.

Given a valid configuration B, we define the graph of B, denoted by G(B), to be the graph whose vertex set is B, and whose edge set is

{{A, B} ⊆ B : A ∩B ≠ ∅}.

A graph is called a block graph if it is the graph of some valid configuration.

Question (C. Thomassen, personal communication) Is there an absolute constant k such that every block graph has chromatic number at most k?

We give a negative answer to the question above. We will show an inductive construction of block graphs with chromatic number k, for each k. The construction uses as a tool a simple coloring lemma which is of independent interest.

Date received: April 3, 2009