Abstract: Graph coloring is a typical NP-completely problem.This paper puts forward a new method of vertex coloring of a graph based on genetic algorithm and heuristics search algorithm.This algorithm involves the coding methods of chromosome,the design of fitness function and the selection operators.Experiments show that this new algorithm can improve time complexity and obtain solutions of excellent quality.

Key words: graph coloring;heuristics search algorithm;genetic algorithm, time complexity