ICS 269, Fall 1996: Theory Seminar
4 Oct 1996:
Geometric Graph Coloring
David Eppstein, ICS, UC Irvine
I will talk about some problems in geometric
graph coloring. The most famous of these is the open
"Hadwiger-Nelson Problem" asking for the maximum chromatic number
of a graph that can be embedded in the plane so that all edges are
exactly one unit long. I'll also discuss some of my recent work on
coloring line
arrangements and quadtrees, and describe another open question
about Penrose
tilings.