Graflar ve kromatik polinomlar

Abstract

Bu çalışmanın amacı çeşitli graf türlerini hatırlamak, grafların kromatik sayılarını ve kromatik polinomlarını hesaplamak, bu hesaplamaları yaparken kullanılabilecek kısa yollar elde etmektir. Bu tez üç bölümden oluşmaktadır. Birinci bölüm giriş bölümüdür. Graf tanımı, tarihçesi, temel kavramlar, kullanım alanları, çeşitli graflar ve özellikleri verilmiştir. Bu bilgiler, bu tez boyunca kullanılacaktır. İkinci bölümde grafların renklendirilmesi ve bu renklendirme için kullanılacak hesaplamalar verilmiştir. Üçüncü bölümde önceki bölümde verilen graflarda renklendirme hesaplamaları için grafları küçültme yolları verilmiştir. Bu bölümde verilen tüm sonuçlar bu tez çalışmasında elde edilmiş orijinal sonuçlardır.

The main aim of this work is to recall several graph types, to calculate chromatic numbers and chromatic polynomials corresponding to these graphs, and to find some better and faster methods to calculate chromatic polynomials. This thesis consists of three chapters. In the first chapter, the fundamental definitions and results are recalled. Definition of graph and related notions, some brief history of graph theory, applications of graph theory, several graph types and their related properties are given. In the second chapter, colouring of graphs and some calculations used for this operation are given. In the third chapter, some new deletion results are given to help finding an easier method to calculate chromatic polynomial of a given graph. All the results obtained in this chapter are original results obtained in this thesis.