A comprehensive research on graph coloring problem

Graph theory is one of the most significant research areas in mathematics due to its wide range of practical applications. In this thesis, we focus specifically on the graph coloring problem. First, we introduce some fundamental concepts. Subsequently, we present key theoretical results concerning existing lower and upper bounds related to graph coloring. Additionally, we discuss essential concepts and foundations of computational complexity theory. Using these, we formally and informally introduce the classes of P and NP problems. Furthermore, we define the class of NP-complete problems and demonstrate, via the Cook-Levin Theorem, that this class is non-empty. Consequently, we establish that determining whether a given graph can be properly colored with a given number of colors k (where k is a natural number) is an NP-complete problem. Although no known polynomial-time algorithm solves this problem optimally, several heuristic algorithms exist in the literature for graph coloring. Among these, we examine the Greedy, DSatur, HEA, and TabuCol algorithms in detail and provide an original comparative analysis based on randomly generated graphs. The graph coloring problem also has real-world applications. We discuss various practical implementations, with a particular focus on examination scheduling, one of its most prominent and widely used applications. In this context, we develop an original design and implement a software solution in Python using Integer Linear Programming (ILP). In conclusion, this thesis serves as a comprehensive Turkish-language resource on graph coloring and computational complexity. Moreover, the developed software will be made available for use by the Department of Mathematics, Faculty of Science, Hacettepe University.