Coloring Hasse diagrams and disjointness graphs of curves

2019/08/22 by Pach, Janos, Tomon, Istvan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.08250

Abstract

Given a family of curves C in the plane, its disjointness graph is the graph whose vertices correspond to the elements of 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 Ω((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.

Related

• Hasse diagrams with large chromatic number
• On the chromatic number of disjointness graphs of curves
• Disjointness graphs of segments
• Disjointness graphs of short polygonal chains
• Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane