Applications of Graph Theory in Computer Science


  • Rashmi Jain Assistant Professor, Department of Mathematics, Government College,Patharia, Madhya Pradesh, India
  • Anuj Kumar Jain Assistant Professor, Department of Mechanical Engineering, Medi-Caps University, Indore, Madhya Pradesh, India


Graph Theory, computer science, data structures, Bipartite graph, networks, Graph coloring, spanning tree, VLSI, Traveling Salesman Problem


Graph theory, a branch of mathematics, has found broad applications in different areas, especially in computer science. This study inspects the basic concepts of graph theory and its different applications in computer science. It talks about the role of graphs in modelling real-world networks, algorithmic problem-solving, optimization, data structures, network analysis, and other significant areas within the domain of computer science. Through different illustrations and case studies, this study aims to illustrate the commonsense importance and wide-ranging applications of graph theory in computer science.


Daruri Venugopal. Applications of Graph Theory in Computer Science Engineering. Int J Sci Technol Manag. 2015; 4(1): 1192–1198.

Mamta Gothwal, Sukhwinder Kaur. Applications of graph theory in computer science. Int J Innov Res Technol. 2015; 1(12): 563–567.

Geetha Narayanan Kannaiyan, Bridjesh Pappula, Ragavi Veerubommu. A Review on Graph Theory in Network and Artificial Intelligence. The open access J Phys: Conf Ser (JPCS). 2021;1831(1): 012002. doi:10.1088/1742-6596/1831/1/012002

Negara ES, Andryani R, Riyan Amanda.Network analysis of Youtube videos based on keyword search with graph centrality approach. Indones J Electr Eng Comput Sci. 2021; 22(2): 780–786.

Abdul Majeed, Ibtisam Rauf.Graph Theory: A Comprehensive Survey about Graph Theory Applications in Computer Science and Social Networks. Inventions. 2020; 5(1): 10(38p).

Besjana Tosuni.Graph Coloring Problems in Modern Computer Science. EurJInterdiscipStud. 2015;1(2): 87–95. doi:10.26417/ejis.v1i2.p87-95

Jakimowicz A,Rzeczkowski D. New measure of economic development based on the four-colour theorem. Entropy. 2021; 23(1): 61.doi:10.3390/e23010061

Dahiya Chetna, Shabnam Sangwan.Literature review on traveling salesman problem. Int J Res. 2018; 5(16): 1152–1155.

Dian Yu, Yanrong Tao, Yue Ma.Solving TSP Problems with Integer Programming. J Phys: Conf Ser. 2022; 2381: 012045. doi: 10.1088/1742- 6596/2381/1/012045

BiswasB, Mitra A,Sengupta S. A Study of Travelling Salesman Problem using Reinforcement Learning over Genetic Algorithm.Turkish Journal of Computer and Mathematics Education (TURCOMAT). 2020; 11(2): 963–981. doi:

Protima Dash, Md. Mosfiqur Rahman,Akter MS. Developing algorithm to obtain the maximum flow in a network flow problem. J Adv Res Dyn Control Syst. 2019; 11(2): 455–459.

Jing Ren, Feng Xia, Xiangtai Chen, Jiaying Liu, Mingliang Hou, Ahsan Shehzad, Nargiz Sultanova, Xiangjie Kong. Matching Algorithms: Fundamentals, applications and challenges. IEEE Trans Emerg Topics Comput Intell. 2021; 5(3): 320–350.