In this paper a new parallel genetic algorithm is proposed to observe efficacy of different strategies for k-graph
coloring problem. In the algorithm we have applied a coarse-grained model of parallelism, along with two new algorithms for crossover and mutation are represented: FCX and Fmm. these algorithms compared with CEX’s First Fit and Transposition mutation operators. In our experiments, we observed that different strategies what role have in finding solutions. In computer simulations of PGA we used DIMACS benchmark.
