Box and segment intersection graphs with large girth and chromatic number

Abstract

We prove that there are intersection graphs of axis-aligned boxes in ${\mathbb{R}}^3$ and intersection graphs of straight lines in ${\mathbb{R}}^3$ that have arbitrarily large girth and chromatic number.

9 pages