Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 10, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Philipp Zumstein
A plane graph is polychromatic k-colorable if there exists a k-coloring of its vertices such that in each face all k colors appear. We will discuss several results implying that a graph is polychromatic 3- or 4-colorable, which have consequences to some variant of the art gallery problem.
A simple bipartite 2-connected plane graph has a polychromatic 3-coloring, which follows from a result by Hoffmann and Kriegel that these graphs admit an even triangulation. Horev and Krakovski have shown that all plane graphs with maximum degree at most 3 are polychromatic 3-colorable with two exceptions. The special graph class of rectangular partitions is polychromatic 4-colorable.
Automatic MiSe System Software Version 1.4803M | admin login