Paras Nath Barwal; Shivam Prakash Mishra; Kamta Nath Mishra

A Novel Machine Learning-Based Approach for Graph Vertex Coloring: Achieving Optimal Solutions with Scalability

PDF (1151KB), PP.98-116

Views: 0 Downloads: 0

Author(s)

Paras Nath Barwal ¹ Shivam Prakash Mishra ¹ Kamta Nath Mishra ^2,*

1. Centre for Development of Advanced Computing (CDAC, Ministry of Electronics & IT, Govt. of India), Noida, India

2. Department of Computer Science & Engg, Birla Institute of Technology, Jharkhand, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2025.05.07

Received: 1 Jan. 2024 / Revised: 20 Oct. 2024 / Accepted: 12 Jun. 2025 / Published: 8 Oct. 2025

Index Terms

Graph Coloring, Integer Programming, Support Vector Machines, Hyperplane, Meta-heuristic, Supervised Learning, Confusion Matrix

Abstract

The challenge of graph vertex coloring is a well-established problem in combinatorial optimization, finding practical applications in scheduling, resource allocation, and compiler register allocation. It revolves around assigning colors to graph vertices while ensuring adjacent vertices have distinct colors, to minimize the total number of colors. In our research, we introduce an innovative methodology that leverages machine learning to address this problem. Our approach involves comprehensive preprocessing of a collection of graph instances, enabling our machine learning model to discern complex patterns and relationships within the data. We extract various features from the graph structures, including node degrees, neighboring node colors, and graph density. These features serve as inputs for training our machine learning model, which can encompass neural networks or decision trees. Through this training, our model becomes proficient at predicting optimal vertex colorings for previously unseen graphs. To evaluate our approach, the authors conducted extensive experiments on diverse benchmark graphs commonly used in vertex coloring research. Our results demonstrate that our machine learning-based approach achieves comparable or superior performance to state-of-the-art vertex coloring algorithms, with remarkable scalability for large-scale graphs. Further, in this research, the authors explored the use of Support Vector Machines (SVM) to predict optimal algorithmic parameters, showing potential for advancing the field. Our systematic, logical approach, combined with meticulous preprocessing and careful optimizer selection, strengthens the credibility of our method, paving the way for exciting advancements in graph vertex coloring.

Cite This Paper

Paras Nath Barwal, Shivam Prakash Mishra, Kamta Nath Mishra, "A Novel Machine Learning-Based Approach for Graph Vertex Coloring: Achieving Optimal Solutions with Scalability", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.17, No.5, pp. 98-116, 2025. DOI:10.5815/ijigsp.2025.05.07

Reference

[1]Leighton F., “A graph coloring algorithm for significant scheduling problems”, Journal of Research of the National Bureau of Standards. 84(6): 489–506, 1979.
[2]Gamst A., “Some lower bounds for a class of frequency assignment problems”, IEEE Transactions on Vehicular Technology, 35(1): 8–14, 1986.
[3]Toft Jensen, B., & R. “Graph Coloring Problems”, Book by John Wiley and Sons, 1-30, 1995.
[4]Welsh T. R., “Pretty graph colouring problems”, Discrete Mathematics, 229(1-3):167–169, 2001.
[5]Wilf H. S., and Bender E. A. “Chromatic Scheduling and the Chromatic Number Problem”, Journal of Algorithms, 6(2): 275–282, 1985.
[6]Brown J. R., “Chromatic Scheduling and the Chromatic Number Problem”, Management Science, 19(4): 456–463, 1972.
[7]Haken W., and & Appel K., “Every Planar graph is four colourable”, Illinois Jour. Math., 21: 429-567, 1976.
[8]Mehrotra A. and & Trick M. A. “A column generation approach for graph coloring”, INFORMS Journal on Computing, 8, 344–354, 1996.
[9]Garey M. R., and Johnson D. S., “Computers and Intractability: A guide to the theory of NP-completeness”, San Francisco, LA: Freeman, 1979.
[10]Méndez-Díaz I., Nasini G., and Severín D., “A polyhedral approach for the equitable coloring problem”, Discrete Applied Mathematics, 164:413–426, 2014.
[11]Méndez-Díaz I., Nasini G., and Severín D., “A dsatur-based algorithm for the equitable coloring problem”, Computers & Operations Research. 57, 41–50, 2015.
[12]Sun W., “Heuristic Algorithms for Graph Coloring Problems”, Data Structures and Algorithms [cs.DS], Université d’Angers, 1-113, 2018. Web Link: https://theses.hal.science/tel-02136810v1/document Last Accessed On: 17.06.2025.
[13]Méndez Diaz I., Nasini G., and & Severin D., “A polyhedral approach for the graph equitable coloring problem”, VI ALIO/EURO Workshop on Applied Combinatorial Optimization.1-6, 2008.
[14]Bahiense L., Frota Y., Noronha T. F., and Ribeiro C. C., “A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives”, Discrete Applied Mathematics. 164: 34–46, 2014.
[15]Furmanczyk H., and Kubale M., “Equitable coloring of graphs”, Contemporary Mathematics. 352: 35–54, 2004.
[16]Méndez Díaz I., Nasini G., and Severín D., “A tabu search heuristic for the equitable coloring problem”, In International Symposium on Combinatorial Optimization. 347–358, 2014.
[17]Xiangjing Lai, Jin-Kao Hao, and Fred G. “Backtracking based iterated tabu search for equitable coloring”, Engg. Apps for AI. Vol. 46, part A, 269-278, 2015.
[18]Brélaz D., “New methods to color the vertices of a graph”, Communications of the ACM. 22(4): 251–256, 1979.
[19]Fleurent C., and Ferland, J.A. “Genetic and hybrid algorithms for graph coloring”, Ann Oper Res. 63, 437–461, 1996.
[20]Porumbel D. C., Hao J., and Kuntz P., “An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring”, Computers & Operations Research. 37(10):1822-1832, 2010.
[21]Tinghan Yang, Rongqing Zhang, Xiang Cheng, and Liuqing Yang, “Graph Coloring Based Resource Sharing (GCRS) Scheme for D2D Communications Underlaying Full-Duplex Cellular Networks”, IEEE Trans on Veh. Networks. pp. 1-12, 2017.
[22]Douiri S.M., and Souad E., “Solving the graph coloring problem via hybrid genetic algorithms”, Journal of King Saud University – Engg Science,27(1): 114-118, 2015.
[23]Yongjian Xu, Huabin Cheng, Ning Xu, Yu Chen, and Chengwang Xie, “A distribution evolutionary algorithm for the graph”, Swarm and Evolutionary Computing, 80: 1-12, 101324, 2023.
[24]Mehrotra A., “Constrained graph partitioning: Decomposition, polyhedral structure, and algorithms”, Ph.D. Thesis, Georgia Institute of Technology, 1992. Web Link: https://www.grafiati.com/en/literature-selections/graph-partitioning-algorithms/dissertation/ Last Accessed On: 17.06.2025.
[25]Sami E., “Support Vector Machines for classification and locating faults on transmission lines”, Applied Soft Computing, 12: 1650–1658, 2012.
[26]Breiman L., Friedman J. H., Olshen R. A., and Stone C. J., “Classification and regression trees. Monterey”, CA: Wadsworth and Brooks/Cole Advanced Books and Software, 769-774, 1984.
[27]Wu J., Gao Z., and Hu C., “An Empirical Study on Several Classification Algorithms and Their Improvements”, In: Cai, Z., Li, Z., Kang, Z., Liu, Y. (eds) Advances in Computation and Intelligence. ISICA 2009. Lecture Notes in Computer Science, 5821: 30–41, 2009.
[28]Chang C.-C. and Lin C.-J., “Training &nu;-support vector classifiers: Theory and algorithms”, Neural Comput. 13, 9, 2119—2147, 2001.
[29]Guyon I., and Elisseeff A., “An introduction to variable and feature selection”, Journal of Machine Learning Research, 3: 1157–1182, 2003.
[30]Schölkopf B., and Smola A. J., “Learning with kernels: support vector machines, regularization, optimization, and beyond”, Adaptive Computation and Machine Learning, MIT Press, 2001.
[31]Cortes C., and Vapnik V., “Support-vector networks”, Mach Learn. 20:273–297, 1995.
[32]Hsu C. W., and Lin C. J., “A comparison of methods for multiclass support vector machines”, IEEE Transactions on Neural Networks. 13(2): 415–425, 2002.
[33]Sun W., Hao J., Zang Y., and Lai Xi. “A solution-driven multilevel approach for graph coloring”, Appl. Soft Comp. 104 (107174): 1-12, 2021.
[34]Zhao R., Wang Y., Liu C. P., Hu, H.,JelodarM. R., and Li H., “Discrete selfish herd optimizer for solving graph coloring problem”, Appl. Intell., 50, 1633-1656, 2020.
[35]Chalupa D., and Nielsen P., “Parameter-free and cooperative local search algorithms”, Soft Computing, Vol. 25, No. 24, 15035-15050, 2021.
[36]Zhong L., Zhou Y., Zhou G., and Luo Q., “Enhanced discrete dragonfly algorithm forsolvingfour-colormapproblems”, ,Appl.Intell.,53: 6372–6400, 2023.
[37]Mirsaleh M. R., and Meybodi M.R., “A michigan memetic algorithm for solving the vertex coloring problem”, J. Comput. Sci., 24: 389–401, 2018.
[38]Silva A.F.D., Rodriguez L.G.A., and Filho J.F., “The improved Colour Ant algorithm: a hybrid algorithm for solving the graph colouring problem”, Int. J. Bio-Inspired Comput., 16(1): 1-12, 2020.
[39]Goudet O., Duval B., and Hao J.K., “Population-based gradient descent weight”, Knowl. Based Syst., 212: 106581, 2021.
[40]Christina G., Athanasios P., Georgios G., and Nectarios K., “High-performance and balanced parallel graph coloring on multicore platforms”. J Supercomput., 79: 6373–6421, 2023.

International Journal of Image, Graphics and Signal Processing (IJIGSP)