A genetic algorithm for total graph coloring

Article type: Research Article

Authors: Dey, Arindam^a | Agarwal, Aayush^b | Dixit, Pranav^b | Long, Hoang Viet^{c; d; *} | Werner, Frank^e | Pal, Tandra^b | Son, Le Hoang^f

Affiliations: [a] Department of Computer Science and Engineering, Saroj Mohan Institute of Technology, Hooghly, India | [b] Department of Computer Science and Engineering, National Institute of Technology, Durgapur, India | [c] Division of Computational Mathematics and Engineering, Institute for Computational Science, Ton Duc Thang University, Ho Chi Minh City, Vietnam | [d] Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam | [e] Faculty of Mathematics, Otto-Von-Guericke University, Magdeburg, Germany | [f] VNU Information Technology Institute, Vietnam National University, Hanoi, Vietnam

Correspondence: [*] Corresponding author. Hoang Viet Long. E-mail: hoangvietlong@tdtu.edu.vn.

Abstract: A genetic algorithm (GA) belongs to the class of evolutionary algorithms and it is one of the most studied heuristic algorithms to solve graph coloring problems. In this paper, we propose a new GA algorithm for the total graph coloring problem. To the best of our knowledge, no algorithm based on a GA exists in the literature for total graph coloring. In the proposed approach, a novel encoding scheme is introduced, where all the edges and vertices of the graph are represented in a chromosome without any repetition. For the initialization of the population, a greedy algorithm is used to determine the total number of colors required for a total coloring of the graph. The number of colors is used as the fitness value of a chromosome which depends on the sequence of vertices and edges representing the chromosome. We introduce a convergence criteria for GA based on the total coloring conjecture. A two-point crossover and mutation operations, suitable for total coloring, are suggested. The proposed algorithm is applied on some well-known and standard graphs. In our computational tests, graphs are used with a maximum number of 690 vertices and 6650 edges of the graph, respectively. The proposed algorithm determines an optimal solution for 21 graphs among the 27 graphs. The solution of remaining the 6 graphs is near optimal and differs by at most one unit from the optimal value. The results show the effectiveness of the proposed approach.

Keywords: Total coloring, total chromatic number, total coloring conjecture, genetic algorithm, crossover, mutation

DOI: 10.3233/JIFS-182816

Journal: Journal of Intelligent & Fuzzy Systems, vol. 37, no. 6, pp. 7831-7838, 2019