Map coloring and course scheduling applications of the graph coloring algorithm based on the malatya centrality algorithm

The Graph Coloring Problem (GCP) was first introduced in 1852 by Francis Guthrie while working on the map of England. Guthrie observed that adjacent regions needed to be colored differently and that this could be achieved using only four colors. Over time, this problem became one of the fundamental topics in graph theory. The primary goal in graph coloring is to assign different colors to adjacent vertices while minimizing the total number of colors used. In this thesis, a novel approach to the graph coloring problem, the Malatya Vertex Coloring (MVC) Algorithm, is proposed. The MVC algorithm calculates the Malatya Centrality (MC) value for each vertex in the graph to identify the most influential node. This node is then colored with a color different from its neighbors and removed from the graph. The process continues until all vertices are colored. The main objective of the algorithm is to reduce the number of colors used and to achieve this within polynomial time. Initially, the proposed algorithm was applied to the graph coloring problem, and subsequently tested on real-world problems such as map coloring and course timetabling. Successful results were obtained on various maps including Asia, Europe, Turkey, U.S. states, and districts of Istanbul. Unlike the classical Four Color Theorem, MVC stands out for its predictability and computational efficiency. Furthermore, the algorithm was applied to the university course timetabling problem, where course conflicts were minimized and valid timetables were generated. The findings demonstrate that the MVC algorithm is a robust, effective, and practical alternative to classical and heuristic-based methods.