Coloring half-planes and bottomless rectangles

DOI10.1016/J.COMGEO.2011.09.004MaRDI QIDQ452449zbMATH OpenOpenAlexFDO

Authors Balázs Keszegh

Publication date 21 September 2012

Published in Computational Geometry (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5764872 (Why is no real title available?)
• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• Coloring axis-parallel rectangles
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Conflict-free coloring of points and simple regions in the plane
• Indecomposable Coverings
• On The Chromatic Number of Geometric Hypergraphs

Cited in

(15)

• Coloring Delaunay-edges and their generalizations
• Colouring games based on autotopisms of Latin hyper-rectangles
• 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
• Coloring points with respect to squares
• Colouring bottomless rectangles and arborescences
• 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)