## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Friday, May 06, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Shakhar Smorodinsky (Courant Inst., New York Univ.)

## On the Chromatic Number of Some Geometric Hypergraphs

A finite family R of simple Jordan regions in the plane defines a hypergraph H=H(R) where the vertex set of H is R and the hyperedges are all subsets S ⊆ R for which there is a point p such that S = {r ∈ R | p ∈ r }. The chromatic number of H(R) is the minimum number of colors needed to color the members of R such that no hyperedge of H(R) is monochromatic. We study the chromatic number of hypergraps that are defined by natural geometric instances such as discs, pseudo discs, axis-parallel rectangles etc. We obtain simple deterministic polynomial time algorithms for coloring such hypergraphs with few'' colors and show how to apply these results to obtain simple deterministic polynomial time algorithms for conflict-free coloring of such regions (where we want the property, that each point that is covered by the regions, is contained in at least one region whose color is unique, i.e., distinct from colors of other regions containing this point) with few'' colors.

Information for students and suggested topics for student talks