Çizge Boyama Problemleri Üzerine Kapsamlı Bir Araştırma

Abstract

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 prob lems. 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 determin ing 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 noknownpolynomial-timealgorithmsolves this problem optimally, several heuris tic 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 Univer sity.