Coloring Intersection Hypergraphs of Pseudo-Disks
- PDF / 582,792 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 201 Views
Coloring Intersection Hypergraphs of Pseudo-Disks Balázs Keszegh1 Received: 13 July 2018 / Revised: 29 September 2019 / Accepted: 9 October 2019 © The Author(s) 2019
Abstract We prove that the intersection hypergraph of a family of n pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with four colors and a conflict-free coloring with O(log n) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of n regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constantly many colors and a conflict-free coloring with O(log n) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks. Keywords Geometric hypergraph coloring · Intersection hypergraph · Delaunay-graph · Pseudo-disks · Regions with linear union complexity
1 Introduction Proper colorings of hypergraphs and graphs defined by geometric regions are studied extensively due to their connections to, among others, conflict-free colorings and to cover-decomposability problems, both of which have real-life motivations in cellular networks, scheduling, etc. For applications and history we refer to the surveys [25,28]. Here we restrict our attention to the (already long list of) results that directly precede our results. We discuss further directions and connections to other problems in Sect. 6.
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach Research supported by the Lendület program of the Hungarian Academy of Sciences (MTA), under the Grant LP2017-19/2017 and by the National Research, Development and Innovation Office—NKFIH under the Grant K 116769. Balázs Keszegh [email protected] 1
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
123
Discrete & Computational Geometry
Our central family of regions is the family of pseudo-disks. Families of pseudodisks have been regarded in many settings for a long time due to being the natural way of generalizing disks while retaining many of their topological and combinatorial properties. Problems regarded range from classic algorithmic questions like finding maximum size independent (disjoint) subfamilies [6] to classical combinatorial geometric questions like the Erd˝os–Szekeres problem [12]. Probably the most important pseudo-disk family is the family of homothets of a convex region. Pseudo-disks are also central in the area of geometric hypergraph coloring problems as we will see soon in this section. Before we state our results and their precursors, we need to introduce some basic definitions. Definition 1.1 Given a hypergraph H, a proper coloring of its vertices is a coloring in which every hyperedge H of size at least 2 of H contains two differently colored vertices. Throughout the paper hy
Data Loading...
