Multi-coloring a graph G is an NP-complete problem that attempts to
define a minimum number of colors for the nodes of a graph where no
adjacent nodes are assigned the same color
[27,32,42]. A greedy polynomial time
heuristic can yield an optimal ordering if the nodes are visited in
the correct order, although the same heuristic may be arbitrarily bad
for a different order [5]. The basic greedy graph
coloring heuristic is presented in figure . The
only aspect of the basic heuristic that is normally modified, as
variations on this algorithm are developed, is the rule to select the
node
from the remaining uncolored nodes [32]. In
adding load-balancing, we have also modified the selection of the
smallest available consistent color.
Figure: The Graph Multi-Coloring Algorithm