  In graph theory, Graph Colouring Problem (GCP) is an assignment of colours to
vertices of any given graph such that the colours on adjacent vertices are
different. The GCP is known to be an optimization and NP-hard problem.
Imperialist Competitive Algorithm (ICA) is a meta-heuristic optimization and
stochastic search strategy which is inspired from socio-political phenomenon of
imperialistic competition. The ICA contains two main operators: the
assimilation and the imperialistic competition. The ICA has excellent
capabilities such as high convergence rate and better global optimum
achievement. In this research, a discrete version of ICA is proposed to deal
with the solution of GCP. We call this algorithm as the DICA. The performance
of the proposed method is compared with Genetic Algorithm (GA) on seven
well-known graph colouring benchmarks. Experimental results demonstrate the
superiority of the DICA for the benchmarks. This means DICA can produce optimal
and valid solutions for different GCP instances.
