Coloring Hasse diagrams and disjointness graphs of curves

Abstract

Given a family of curves $\mathcal{C}$ in the plane, its disjointness graph is the graph whose vertices correspond to the elements of $\mathcal{C}$, and two vertices are joined by an edge if and only if the corresponding sets are disjoint. We prove that for every positive integer $r$ and $n$, there exists a family of $n$ curves whose disjointness graph has girth $r$ and chromatic number $\Omega (\frac{1}{r}\log n)$. In the process we slightly improve Bollobás's old result on Hasse diagrams and show that our improved bound is best possible for uniquely generated partial orders.

arXiv commentAppears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)