In this paper

we present a graph simplifying method which is fit for graph coloring problem. In this method

each node is deleted whenever its degree in the attained graph is less than a certain value. When graph coloring algorithms are combined with this simpliying method

their performances can be improved. We also exploit the schemes of setting the value and combining this method with GAs

and show the promising results of the simulation. Finally

it is pointed out that the method is also fit for other graph problems such as the largest clique

maximum independent set

etc.