Graf boyama üzerine / On graph colori̇ng

Abstract

Bu tezde öncelikle graf teorisinin ve graf boyamanın tarihi gelişimi üzerine bilgiler verilmiştir. Daha sonra ise graflarda boyama ölçümleri üzerine günümüze kadar yapılan çalışmalarda elde edilen bilgilere yer verilmiştir. Ardından da graf işlemleri boyaması çalışılmıştır. İlk bölümde, graf boyamanın tarihsel gelişiminden bahsedilmiştir. Tezimizin İkinci bölümünde, bu tezi anlamada kolaylık sağlayacak temel graf tanımlarına yer verilmiştir. Üçüncü bölümde graflarda boyama ölçümlerinden bir tanesi olan tepe boyama incelenmiş ve tanımlara yer verilmiştir. Ayrıca bazı özel graflarda tepe boyama incelenerek, bu özel grafların kromatik sayıları hesaplanmıştır. Son olarakta tepe boyama algoritmaları ve tepe boyamanın uygulama alanlarından bahsedilmiştir. Tezimizin dördüncü bölümünde kenar boyama incelenmiş ve kenar boyama ile ilgili tanımlardan bahsedilmiştir. Graf boyama ölçümlerinden biri olan kenar boyama için gerekli olan en az renk sayısı bazı özel graflarda gösterilmiştir. Son bölümde ise graf işlemlerine yer verilmiş ve graf işlemleri sonucunda elde edilen bazı grafların boyama örnekleri çalışılmıştır. Anahtar Kelime: Graf boyama tarihi, tepe boyama, kenar boyama, graf işlemleri boyaması In this thesis firstly the historical development of graph theory and graph coloring are studied. Then knowledge obtained from studies made on graph coloring measurements until today are analyzed. Consequently graph operations coloring are studied. The first part of the thesis includes the historical development of graph coloring. The second part consists of the basic graph definitions which will help readers to understand this thesis. In the third part one of the graph coloring measurements which is the vertex coloring is studied and definitions are included. Also vertex coloring for some special graph is analyzed and chromatic numbers of these special graphs are calculated. Finally in this part vertex coloring algorithms and application areas of vertex coloring are studied. The forth part of the thesis includes edge coloring and concerned definitions. The minimum number of colors required for edge coloring, which is one of the measurement of graph coloring, is shown on some special graphs. In the last part, graph operations are mentioned and the examples of coloring of some graphs that are obtainedd after graph operations are studied. Keywords: History of graph coloring, vertex coloring, edge coloring, graph operations coloring