Heuristic Graph Coloring Algorithm
Jihad M. Jaam and Ahmad M. Hasnah
University of QATAR, College of Science, Computer Science Department,
Doha, QATAR,
E-mails: jaam@qu.edu.qa , hasnah@qu.edu.qa
 

Abstract:
In this paper we are interested in the graph coloring problem. We propose a stochastic algorithm based on optimization technique and different greedy strategies to generate valid approximate k-colorings for random graphs of the class Gn,n,p The algorithm finds k-colorings for the standard graph instance g1000,1 wth k varies from 86 to 105 which are promising results compared to those given in [3, 9, 13, 29].
Keywords : Greedy Graph, Heuristic Optimization