Çizgelerde yol-eşleme ve renklendirme
Path-matching and coloring in graphs
Yazar: ZAKİR DENİZ
Danışman: DOÇ. DR. YUSUF CİVAN
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Yüksek Lisans, 2012
Konu: Matematik = Mathematics
Dizin: Matematik = Mathematics

Özet:
Bu tezde, çizgelerde yol-bileşen, yol-eşleme ve renklendirme konusu ele alınmıştır. Çalışmanın amacı, çizgelerde yol-bileşen ve eşleme kavramlarının ele alınıp, çizgelerde renklendirme ile ilgili bilinen bazı teorem ve savlar hakkında yeni bulgular ortaya koymaktır.Çalışma altı bölümden oluşmaktadır ve her bir bölüm, okuyucunun çizgelerde yol-bileşen, eşleme ve renklendirme kavramları arasındaki ilişkileri anlayabileceği şekilde hazırlanmıştır. İlk bölümde, kullanılan tüm notasyonlar ile birlikte temel motivasyonumuz açık bir şekilde ifade edilmiştir. Ayrıca elde ettiğimiz yeni sonuçlar listelenmişir. İkinci bölümde ise bu çalışma boyunca ihtiyaç duyduğumuz bazı temel tanım ve kavramlara yer verilmiştir.Üçüncü ve dördüncü bölümlerde, çizgelerde eşleme ve bileşen konusu ele alınmıştır. Özellikle dördüncü bölümde, tüm regüler çizgeler için (P_2,P_3)-bileşenin mevcut olduğu ispatlanmıştır. Bu sonuç yardımıyla herhangi bir çizgede tüm maksimum dereceli köşeleri doyuran bir yol-eşlemenin mümkün olduğu ispatlanmıştır. Bu bölümde ek olarak, yol-eşleme kavramının maksimize edilmesiyle, herhangi bir çizgeden maksimal yol-eşlemenin çıkarılması durumunda maksimum derecenin en az bir 1 azalması sonucu elde edilmiştir. Bu gerçek, König ve Vizing Teoremlerinin alternatif birer ispatlarının verilmesini sağlamıştır. Böyle bir yaklaşım iyi bilinen Total Renklendirme Savının özel bir durumunu kanıtlamamıza olanak vermiştir. Tezin kalan kısmında Reed & Kostachka Savı ele alınmıştır. i(G), bağımsız baskınlık sayısı olmak üzere, üçgen-yoksun bir G çizgesinin köşe kromatik sayısı için i(G)+1 olacak şekilde bir üst sınır elde edilmiştir. Bunun yanı sıra üçgen-yoksun çizgeler üzerinde bir algoritma (Return Algorithm) geliştirerek iyileştirilmiş bir üst sınır verilmiştir. Bu sonuç, i(G) ? ?/2+1 olan üçgen-yoksun çizgeler için Reed Savının doğruluğunu ispat etmektedir.Sonuç bölümünde, elde edilen sonuçlar değerlendirilmiştir. Ayrıca bazı açık problemler ve ileride mümkün olabilecek projeler ifade edilmiştir.

Abstract:
In this thesis, path-factor, path-matching and graph coloring are studied. Aim of this work is to examine the notions of path-factor and matching in graphs, and to present some new findings related to some well-known theorems and conjectures in graph theory.This study consists of six chapters, and each chapter prepares its readers to understand the interrelations of path-factor, matching and coloring of graphs. In the first chapter, we explicitly describe our motivation to study these notions all together. There, we also list some of the new results of this thesis. The second chapter provides some of the basic definitions and known results that are needed throughout the thesis.In chapters three and four, we study matchings and factors in graphs. In particular, the existence of (P_2,P_3)-factor for all regular graphs is proven in chapter four. With the help of this result, we are able to show that there exists a path-matching in any graph that saturates all vertices of maximum degree. Additionally, by maximizing the existing path-matching we conclude that the maximum degree of any graph can be reduced at least by one if we remove the maximal path-matching. This fact enables us to supply alternative proofs of classical theorems of König and Vizing on edge colorings of graphs. Such an approach permits us to prove a special case of the well-known Total Coloring Conjecture. The remainder of this thesis deals with Kostachka & Reed's Conjecture. We prove that the (vertex) chromatic number of triangle free graphs is always bounded above by i(G)+1, where i(G) is the independent domination number of G. Furthermore, we provide an algorithm (Return Algorithm) on triangle free graphs that enables to test tightness of the stated upper bound. This result also shows the accuracy of Reed?s conjecture for all triangle-free graphs with i(G) ? ?/2+1.In the conclusion chapter, we review the results of this thesis. We there also state some open problems and possible future projects.