Coloring half-planes and bottomless rectangles

DOI10.1016/J.COMGEO.2011.09.004zbMATH Open1248.05068arXiv1105.0169OpenAlexW2016829899MaRDI QIDQ452449FDOQ452449

Authors: Balázs Keszegh 

Publication date: 21 September 2012

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: We prove lower and upper bounds for the chromatic number of certain hypergraphs defined by geometric regions. This problem has close relations to conflict-free colorings. One of the most interesting type of regions to consider for this problem is that of the axis-parallel rectangles. We completely solve the problem for a special case of them, for bottomless rectangles. We also give an almost complete answer for half-planes and pose several open problems. Moreover we give efficient coloring algorithms.

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

Recommendations

• Colouring bottomless rectangles and arborescences
• Polychromatic coloring for half-planes
• Polychromatic coloring for half-planes
• On coloring points with respect to rectangles
• Coloring hypergraphs induced by dynamic point sets and bottomless rectangles
• Entire colouring of plane graphs
• scientific article; zbMATH DE number 2112064
• On colorings of finite projective planes
• A Coloring Result for the Plane
• scientific article; zbMATH DE number 866019

zbMATH Keywords

half-planegeometric hypergraphconflict-free coloringaxis-parallel rectangleproper hypergraph coloring

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring of points and simple regions in the plane
• On The Chromatic Number of Geometric Hypergraphs
• Indecomposable Coverings
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloring axis-parallel rectangles

Cited In (15)

• Colouring games based on autotopisms of Latin hyper-rectangles
• Coloring Delaunay-edges and their generalizations
• Proper coloring of geometric hypergraphs
• Online and quasi-online colorings of wedges and intervals
• Polychromatic colorings of unions of geometric hypergraphs
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Coloring intersection hypergraphs of pseudo-disks
• Polychromatic coloring for half-planes
• On The Chromatic Number of Geometric Hypergraphs
• Colouring bottomless rectangles and arborescences
• Coloring points with respect to squares
• Discrete Helly-type theorems for pseudohalfplanes
• Coloring hypergraphs induced by dynamic point sets and bottomless rectangles
• Coloring intersection hypergraphs of pseudo-disks
• Octants are cover-decomposable into many coverings

This page was built for publication: Coloring half-planes and bottomless rectangles

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