Graph Embeddings and Approximate Graph Coloring
by François Labelle
under the supervision of Prof. Sue Whitesides
We describe how to embed a graph into a small n-dimensional hypersphere such that the endpoints of any edge are placed exactly one unit of distance apart. As an application, we show how such an embedding can be used to find large independent sets in sparse 3-colorable graphs. By combining this algorithm with another which is specialized in dense graphs, we obtain a randomized, polynomial time algorithm that can color any 3-colorable graph using at most O(n1/4log1/2n) colors.
Download gzipped postscript
page last updated: October 7, 2001