DSpace Repository

Çizgelerde yol-eşleme ve renklendirme = Path-matching and coloring in graphs /

Show simple item record

dc.creator Deniz, Zakir, 1987- author 30905
dc.creator Süleyman Demirel Üniversitesi. Fen Bilimleri Enstitüsü. Kimya Anabilim Dalı. issuing body 9868
dc.creator Civan, Yusuf, 1971- thesis advisor 14590
dc.date 2012.
dc.identifier http://tez.sdu.edu.tr/Tezler/TF01986.pdf
dc.description 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 yolbileş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 (P2,P3)-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. Anahtar Kelimeler: Yol-eşleme, yol-bileşen, çizgelerde renklendirme, Vizing Teoremi.
dc.description 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 (P2,P3)-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 wellknown 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. Keywords: Path-matching, path-factor, coloring of graphs, Vizing‟s Theorem.
dc.description Tez (Yüksek Lisans) - Süleyman Demirel Üniversitesi, Fen Bilimleri Enstitüsü, Matematik Anabilim Dalı, 2012.
dc.description Kaynakça var.
dc.description 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 yolbileş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 (P2,P3)-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. Anahtar Kelimeler: Yol-eşleme, yol-bileşen, çizgelerde renklendirme, Vizing Teoremi.
dc.description 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 (P2,P3)-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 wellknown 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. Keywords: Path-matching, path-factor, coloring of graphs, Vizing‟s Theorem.
dc.language tur
dc.publisher Isparta : SDÜ Fen Bilimleri Enstitüsü,
dc.subject Süleyman Demirel Üniversitesi
dc.title Çizgelerde yol-eşleme ve renklendirme = Path-matching and coloring in graphs /
dc.type text


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account