Box-Delaunay graphs of large chromatic number

Abstract

For every $n$, we construct a 2-dimensional $n$-element poset whose Hasse diagram has independence number $n\exp (-\Omega (\sqrt{\log n}))$, and consequently, chromatic number $\exp (\Omega (\sqrt{\log n}))$. This also yields an $n$-point planar set whose box-Delaunay graph satisfies the same bounds.

6 pages, 2 figures