Coloring Hasse diagrams and disjointness graphs of curves

DOI10.1007/978-3-030-35802-0_19MaRDI QIDQ6324024arXivWikidataFDO

Authors János Pach, István Tomon

Publication date 22 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-35802-0_19

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

math.CO

Abstract: Given a family of curves $mathcalC$ in the plane, its disjointness graph is the graph whose vertices correspond to the elements of $mathcalC$, 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(frac1rlogn)$. In the process we slightly improve Bollob'as's old result on Hasse diagrams and show that our improved bound is best possible for uniquely generated partial orders.

This page was built for publication: Coloring Hasse diagrams and disjointness graphs of curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324024)