#
Culberson's Graph Coloring Research

## Randomized Approaches to NP-Complete Problems

Graph Coloring and Clique finding are two NP-complete
optimization problems which
are also known, by recent results, to be hard to approximate.
On the other hand, it is also known that
for a graph drawn at random from all *n*-vertex graphs,
the simple greedy algorithm will yield a coloring within a factor of two
with high probability. Iterative techniques can do much better in reasonable
time.
This research focuses on the two-sided approach of trying to find better
iterative and heuristic algorithms, and to determine the limits of
these approaches over various classes of graphs. For this latter objective,
it is useful to determine classes of graphs which thwart these
and most other algorithms.

In coloring, **
TR92-07: Iterated Greedy Graph Coloring and the Difficulty Landscape
**
surveys some previous coloring approaches,
describes my Iterated Greedy Approach, and surveys the landscape of
*k*-colorable graphs using a mixture of approaches.
Also available is a
**
searchable bibliography **
of coloring and clique related references
in bibtex format and also in compressed postscript format.
I welcome additional references, and error corrections; these should be sent to
* joe@cs.ualberta.ca *.

In a paper presented at the DIMACS
for the
Second Challenge on Cliques, Graph Coloring and Satisfiability,
co-authored with Feng Luo, and titled
**
Exploring the ***k*-colorable Landscape with Iterated Greedy
we extended the experimental results and the classes of graphs to
ones with up to ten thousand vertices.
At the same workshop, Mark Brockington presented joint work on the difficulty
of hiding independent sets in graphs **
Camouflaging Independent Sets in Quasi-Random Graphs.
**

See also Mike Trick's site
Second Challenge.

As with many such problems, the difficult instances in graph coloring seem
to be found mostly on a narrow ``ridge'' of graphs with particular properties.
Current research is focused on better understanding the structures and
qualities that make up the graphs found in this region of graph space.

A study looking for harder classes of graphs was presented at the
CP95 Workshop on
Studying and Solving Really Hard Problems held
September 23, 1995 in Cassis, France.
This paper,
Hiding our colors
co-authored with Adam Beacham and Denis Papp,
presents first results from a generating program
available here.
(The paper is also available via
ftp://ftp.cs.ualberta.ca/pub/joe/Preprints/ssrhpclr.ps.gz).
This program generates graphs
which have a hidden $k$-coloring.

Joseph Culberson

* Nov 21, 1995 *