BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Coloring hypergraphs defined by pseudo-disks Keszegh, Balázs


We present several results about coloring geometric hypergraphs that are defined by pseudo-disk arrangements. In particular, we prove that the intersection hypergraph of a finite family of pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors. Along the way we prove that the corresponding Delaunay-graph is planar. Our results serve as a common generalization and strengthening of many earlier results, including ones about coloring points with respect to pseudo-disks, coloring pseudo-disks with respect to points and coloring disks with respect to disks.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International