Proper coloring of geometric hypergraphs

DOI10.4230/LIPICS.SOCG.2017.47MaRDI QIDQ4580123zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2018

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

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)

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.

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

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 points with respect to squares
• Coloring hypergraphs defined by stabbed pseudo-disks and \(ABAB\)-free hypergraphs
• 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)