{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T06:36:46Z","timestamp":1777703806796,"version":"3.51.4"},"reference-count":30,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"published-print":{"date-parts":[[2019,12,23]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3233\/jifs-182816","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T13:33:55Z","timestamp":1573220035000},"page":"7831-7838","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["A genetic algorithm for total graph coloring"],"prefix":"10.1177","volume":"37","author":[{"given":"Arindam","family":"Dey","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Saroj Mohan Institute of Technology, Hooghly, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aayush","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Durgapur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranav","family":"Dixit","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Durgapur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoang Viet","family":"Long","sequence":"additional","affiliation":[{"name":"Division of Computational Mathematics and Engineering, Institute for Computational Science, Ton Duc Thang University, Ho Chi Minh City, Vietnam"},{"name":"Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Otto-Von-Guericke University, Magdeburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tandra","family":"Pal","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Durgapur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Le Hoang","family":"Son","sequence":"additional","affiliation":[{"name":"VNU Information Technology Institute, Vietnam National University, Hanoi, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2019,11,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90146-7"},{"key":"e_1_3_1_3_2","article-title":"Upper bounds of chromatic functions of graphs","author":"Kostochka A.","year":"1978","unstructured":"KostochkaA., Upper bounds of chromatic functions of graphs, Doct Thesis (1978).","journal-title":"Doct Thesis"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00286-6"},{"key":"e_1_3_1_5_2","unstructured":"DharwadkerA. The vertex coloring algorithm available on http:\/\/www. geocities.com\/dharwadker\/vertex coloring (2006)."},{"key":"e_1_3_1_6_2","first-page":"805","article-title":"The fuzzy robust graph coloring problem","volume":"2014","author":"Dey A.","year":"2015","unstructured":"DeyA., PradhanR., PalA. and PalT., The fuzzy robust graph coloring problem, Proc. of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2014 (2015), 805\u2013813.","journal-title":"Proc. of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA)"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125407"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02430368"},{"key":"e_1_3_1_9_2","article-title":"Total colourings of graphs","volume":"1623","author":"Yap H.P.","year":"1984","unstructured":"YapH.P., Total colourings of graphs, Lecture Notes in Mathematics 1623 (1984).","journal-title":"Lecture Notes in Mathematics"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0778-8"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","unstructured":"DavisL. . Handbook of genetic algorithms 115 (1991).","DOI":"10.1016\/B978-0-08-050684-5.50011-2"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2009.03.009"},{"issue":"3","key":"e_1_3_1_13_2","first-page":"52","article-title":"On the vertex strong total coloring of graphs","volume":"15","author":"Linzhong L.","year":"1998","unstructured":"LinzhongL., JiguoX. and ZhongfuZ., On the vertex strong total coloring of graphs, Mathematics in Economics 15(3) (1998), 52\u201355.","journal-title":"Mathematics in Economics"},{"key":"e_1_3_1_14_2","unstructured":"BehzadM. Graphs and their chromatic numbers Ph.D. thesis (1965)."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771690"},{"key":"e_1_3_1_16_2","first-page":"180","article-title":"On the total coloring of planar graphs","volume":"394","author":"Borodin O.V.","year":"1989","unstructured":"BorodinO.V., On the total coloring of planar graphs, J reine angew Math 394 (1989), 180\u2013185.","journal-title":"J reine angew Math"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009625526657"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009823419804"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056916"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0620-5"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1070\/RM1968v023n06ABEH001252"},{"key":"e_1_3_1_22_2","first-page":"161","volume-title":"Heuristics: Theory and Applications","author":"Werner F.","year":"2013","unstructured":"WernerF., A Survey of Genetic Algorithms for Shop Scheduling Problems, in: SiarryP. (ed.) Heuristics: Theory and Applications, Nova Science Publishers (2013), 161\u2013222."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00358-9"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1360\/03YS0207"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11425-007-0128-y"},{"key":"e_1_3_1_26_2","first-page":"2","article-title":"Uniform Crossover in Genetic Algorithms","author":"Syswerda G.","year":"1989","unstructured":"SyswerdaG., Uniform Crossover in Genetic Algorithms, Proceedings of Third International Conference on Genetic Algorithms (1989), 2\u20139.","journal-title":"Proceedings of Third International Conference on Genetic Algorithms"},{"key":"e_1_3_1_27_2","article-title":"Uniform Random Crossover","author":"Jones S.","year":"2007","unstructured":"JonesS. and HindeJ., Uniform Random Crossover, Proceedings of the 2007 workshop on Computational Intelligence (2007).","journal-title":"Proceedings of the 2007 workshop on Computational Intelligence"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9954-y"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-018-1262-7"},{"key":"e_1_3_1_30_2","unstructured":"LongH.V. AliM. SonL.H. KhanM. and TuD.N. A novel approach for Fuzzy Clustering based on Neutrosophic Association Matrix Computers and Industrial Engineering."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.09.027"}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-182816","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JIFS-182816","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-182816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:39:40Z","timestamp":1777455580000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JIFS-182816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,8]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,23]]}},"alternative-id":["10.3233\/JIFS-182816"],"URL":"https:\/\/doi.org\/10.3233\/jifs-182816","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,8]]}}}