Coloring intersection hypergraphs of pseudo-disks

DOI10.4230/LIPICS.SOCG.2018.52zbMATH Open1491.05139arXiv1711.05473MaRDI QIDQ5115820FDOQ5115820

Authors: Balázs Keszegh 

Publication date: 18 August 2020

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 $4$ colors and a conflict-free coloring with $O(logn)$ 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(logn)$ 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.

Full work available at URL: https://arxiv.org/abs/1711.05473

Recommendations

• Coloring intersection hypergraphs of pseudo-disks
• On The Chromatic Number of Geometric Hypergraphs
• Proper coloring of geometric hypergraphs
• Proper coloring of geometric hypergraphs
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs

zbMATH Keywords

combinatorial geometryconflict-free coloringgeometric hypergraph coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Indecomposable coverings with homothetic polygons
• An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes
• Unsplittable coverings in the plane
• Octants are cover-decomposable
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Survey on Decomposition of Multiple Coverings
• Conflict-Free Coloring and its Applications
• On The Chromatic Number of Geometric Hypergraphs
• Coloring planar homothets and three-dimensional hypergraphs
• Indecomposable Coverings
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Conflict-free coloring of intersection graphs of geometric objects
• On the boundary of the union of planar convex sets
• Approximation algorithms for maximum independent set of pseudo-disks
• Coloring half-planes and bottomless rectangles
• Title not available (Why is that?)
• Toward a theory of crossing numbers
• Über wesentlich unplättbare Kurven im dreidimensionalen Raume
• Topological Hypergraphs
• On pseudo-disk hypergraphs
• Coloring points with respect to squares
• More on decomposing coverings by octants
• Proper Coloring of Geometric Hypergraphs
• A Finite Family of Pseudodiscs Must Include a “Small” Pseudodisc
• Two extensions of the Erdős-Szekeres problem
• Adjacent Crossings Do Matter

Cited In (7)

• On pseudo-disk hypergraphs
• Conflict-free coloring of string graphs
• On The Chromatic Number of Geometric Hypergraphs
• Conflict-free coloring of intersection graphs of geometric objects
• Conflict-free colouring of subsets
• Constructing planar support for non-piercing regions
• Existence of planar support for geometric hypergraphs using elementary techniques

This page was built for publication: Coloring intersection hypergraphs of pseudo-disks

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