Analysis and classification of heuristic algorithms for the node coloring problem

The node coloring problem is a problem to color the nodes of a graph using the minimum number of colors possible so that any two adjacent nodes are colored differently. This problem, along with the edge coloring problem, has a variety of practical applications particularly in item loading, resource allocation, exam timetabling, and channel assignment. The node coloring problem is an NP-hard problem, and thus many researchers develop a number of heuristic algorithms. In this paper, the authors survey and classify those heuristics with the emphasis on how an algorithm orders the nodes and colors the nodes using a determined ordering. [In Korean.]