Proper coloring of geometric hypergraphs

DOI10.4230/LIPICS.SOCG.2017.47zbMATH Open1430.68377arXiv1612.02158OpenAlexW2962969880MaRDI QIDQ4580123FDOQ4580123

Authors: Balázs Keszegh, Dömötör Pálvölgyi 

Publication date: 13 August 2018

Abstract: We study whether for a given planar family F there is an m such that any finite set of points can be 3-colored such that any member of F that contains at least m points contains two points with different colors. We conjecture that if F is a family of pseudo-disks, then such an m exists. We prove this in the special case when F is the family of all homothetic copies of a given convex polygon. We also study the problem in higher dimensions.

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

Recommendations

• Proper coloring of geometric hypergraphs
• Coloring Planar Homothets and Three-Dimensional Hypergraphs
• Coloring planar homothets and three-dimensional hypergraphs
• Coloring intersection hypergraphs of pseudo-disks
• Coloring intersection hypergraphs of pseudo-disks

zbMATH Keywords

discrete geometrygeometric hypergraph coloringdecomposition of multiple coverings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Erd?s problems and related topics of discrete geometry (52C10)

Cited In (13)

• Colorful strips
• Proper coloring of geometric hypergraphs
• Polychromatic colorings of unions of geometric hypergraphs
• Coloring intersection hypergraphs of pseudo-disks
• On proper colourings of hypergraphs using prescribed colours
• Coloring Geometric Range Spaces
• Coloring hypergraphs defined by stabbed pseudo-disks and \(ABAB\)-free hypergraphs
• Coloring points with respect to squares
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
• Colorful strips
• Coloring intersection hypergraphs of pseudo-disks
• Coloring planar homothets and three-dimensional hypergraphs
• Coloring geometric range spaces

This page was built for publication: Proper coloring of geometric hypergraphs

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