Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login