Abstract

In this project we search for maximum cliques in some random graphs and random k-partite graphs, using either the greedy coloring algorithm or the Dsatur coloring algorithm as bounding functions. We compare the efficiency of the algorithms by looking at the sizes of the resulting state space trees, as well as the number of colors required by the respective coloring algorithms. Finally, we implement a bichromatic interchange algorithm in an attempt to improve the coloring algorithms.