The memetic algorithms proposed in the literature for graph coloring typically use a small population with no more than 100 individuals. At each generation, one offspring solution is usually created by a crossover (or recombination) operator applied to two or more randomly selected individuals from the population. One of the most popular crossovers used for graph coloring problems is the Greedy Partition Crossover (GPX) introduced in the hybrid evolutionary algorithm (HEA) [1]}. The GPX operator produces offspring by inheriting alternatively the largest color classes in the parent solutions. The resulting offspring is then improved by a local search procedure such as TabuCol [2]}.
