## DIMACS TR: 94-35

## A spectral technique for coloring random 3-colorable graphs

### Authors: Noga Alon and Nabil Kahale

**
ABSTRACT
**

Let $G_{3n,p,3}$ be a random $3$-colorable graph on a set of $3n$ vertices
generated as follows. First, split the vertices arbitrarily into three equal
color classes and then choose every pair of vertices of distinct color classes,
randomly and independently, to be an edge with probability $p$. We
describe a polynomial time algorithm that finds a proper $3$-coloring of
$G(3n,p,3)$ with high probability, whenever $p \ge c /n$. where $c$ is
a sufficiently large absolute constant. This settles a problem of Blum and
Spencer, who asked if one can design an algorithm that works almost surely for
$p \ge polylog(n) /n$. The algorithm can be extended to produce optimal
$k$-colorings of random $k$-colorable graphs in a similar model, as well as
in various related models. Implementation results show that the algorithm
performs very well in practice even for moderate values of $c$.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-35.ps

DIMACS Home Page