ICS Theory Group

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.