Box and segment intersection graphs with large girth and chromatic number

The chromatic number of a graph, i.e., the minimum number of colors required to color its vertices so that no two adjacent vertices have the same color, is one of the most intriguing graph parameters. Clearly, the chromatic number of a graph is at least its clique number, i.e., the maximum number of vertices in the graph that are pairwise adjacent. On the other hand, there is no function \(f\) for which the chromatic number of a graph with clique number \(\omega\) is at most \(f(\omega)\). Even more generally, there exist graphs with arbitrarily large chromatic number and no cycle of length at most \(\ell\) for any fixed \(\ell\), which is a more restrictive condition than bounding the clique number.

This paper concerns graphs that can be represented as intersection graphs of geometric objects. For example, interval graphs are graphs such that their vertices can be associated with intervals on the real line and two vertices are adjacent if (and only if) the associated intervals intersect. It is well-known that the chromatic number of every interval graph is equal to its clique number. Asplund and Grünbaum in 1960 proved that the chromatic number of intersection graphs of axis-parallel rectangles is bounded by a function of its clique number but Burling in 1965 showed that the same is not true for intersection graph of 3-dimensional axis-parallel boxes. In particular, he showed that there exist such intersection graphs that are triangle-free and have arbitrary large chromatic number. One of the two main results of this paper goes further (while the other asserts the same for intersection graphs of straight lines in 3-dimensional space): for every \(\ell\) and \(k\), there exists an intersection graph of 3-dimensional axis-parallel boxes that has no cycle of length less than \(\ell\) and its chromatic number is at least \(k\).