Graph Embeddings and Approximate Graph Coloring

by François Labelle

under the supervision of Prof. Sue Whitesides

May 2000

Abstract

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(n^1/4log^1/2n) colors.

Download gzipped postscript

embedcolor-1s.ps.gz (single-sided version, large margins are on the left)
embedcolor-2s.ps.gz (double-sided version, large margins alternate left/right)

page last updated: October 7, 2001