Bu tez çalışmasında karşılaştırılabilirlik çizgelerinin karelerinin karakterizasyonu, karşılaştırılabilir çizgelerinin bazı alt sınıfları ve bazı genel çizge sınıfları için karesel renklendirme konuları ele alınmıştır. Bu çalışmanın temel amacı karşılaştırılabilirlik çizgelerinin karelerini karakterize ederek, karşılaştırılabilirlik çizgelerinin ve köşe sıralama karakterizasyonuna ya da aralık gösterimine sahip olan bazı genel çizge sınıflarının karesel kromatik sayıları için sıkı üst sınırlar elde etmektir. Dört bölümden oluşan bu tezin ilk bölümünde çalışma ile ilgili literatür bilgileri ve motivasyon sunulurken, ikinci bölümde çalışma boyunca kullanılacak olan bazı temel bilgilere yer verilmiştir. Üçüncü bölümde, önce karşılaştırılabilirlik çizgelerinin karelerinin karakterizasyonları verilerek ardından karşılaştırılabilirlik çizgelerinin karelerinin renklendirilmesi problemi incelenmiştir. Bu kapsamda, zayıf üçgensel iki-parçalı çizgeler, aralık sıralarının karşılaştırılabilirlik çizgeleri, boyutu 2 olan kısmi sıralı kümelerin karşılaştırılabilirlik çizgeleri, ağaç-benzeri ve üçgensel karşılaştırılabilirlik çizgelerinin karelerinin renklendirmeleri için üst sınırlar verilerek, yüksekliği 3 olan kısmi sıralı kümelerin karşılaştırılabilirlik çizgeleri ve zayıf üçgensel karşılaştırılabilirlik çizgelerinin karesel renklendirmesi için özel durumlar altında üst sınırlar elde edilmiştir. Son bölümde çeşitli genel çizge sınıflarının karesel renklendirilmesi problemi ele alınmıştır. Köşe sıralama karakterizasyonlarından faydalanılarak güçlü sıralanabilir, dual üçgensel, güçlü üçgensel, üçgensel ve ardıl-karşılaştırılabilirlik çizgelerinin karesel kromatik sayıları için üst sınırlar elde edilmiştir. Ayrıca aralık temsilleri yardımıyla aralık, ardıl-aralık, aralık kapsama (permütasyon) çizgeleri ve aralık k-çizgelerinin karelerinin kromatik sayıları için üst sınırlar verilmiştir.
In this thesis, characterization and coloring of the square of comparability graphs are studied. Square colorings of various general graph classes are further investigated. The main goal of this dissertation is to characterize squares of comparability graphs and provide tight upper bounds on the chromatic number of squares of comparability graphs and graphs which admit a vertex ordering characterization or an interval representation. This thesis consists of four chapters. First chapter presents a brief summary of literature, while the second chapter provides preliminary definitions and notations used throughout the study. In chapter three, we characterize squares of comparability graphs and provide upper bounds on the chromatic number of the squares of chordal bipartite graphs, comparability graphs of interval orders, treelike comparability graphs, chordal comparability graphs and comparability graphs of posets of dimension at most 2. We also give sufficient conditions on weakly chordal comparability graphs and the comparability graphs of posets of height 3, to have the desired upper bounds on their square coloring. In the final chapter, we deal with the coloring of squares of graphs which have a vertex ordering characterization or an interval representation. We establish upper bounds on the chromatic number of the square of strongly orderable, dually chordal, strongly chordal, chordal and cocomparability graphs, by appealing to their vertex ordering characterizations. We further provide upper bounds on the chromatic number of the squares of interval, co-interval, interval containment (permutation) and interval k-graphs by using their interval representations. Keywords: comparability graph, square of graph, coloring, square coloring, distance-2 coloring, vertex ordering, interval representation.
Tez (Doktora) - Süleyman Demirel Üniversitesi, Fen Bilimleri Enstitüsü, Matematik Anabilim Dalı, 2019.
Kaynakça var.
Bu tez çalışmasında karşılaştırılabilirlik çizgelerinin karelerinin karakterizasyonu, karşılaştırılabilir çizgelerinin bazı alt sınıfları ve bazı genel çizge sınıfları için karesel renklendirme konuları ele alınmıştır. Bu çalışmanın temel amacı karşılaştırılabilirlik çizgelerinin karelerini karakterize ederek, karşılaştırılabilirlik çizgelerinin ve köşe sıralama karakterizasyonuna ya da aralık gösterimine sahip olan bazı genel çizge sınıflarının karesel kromatik sayıları için sıkı üst sınırlar elde etmektir. Dört bölümden oluşan bu tezin ilk bölümünde çalışma ile ilgili literatür bilgileri ve motivasyon sunulurken, ikinci bölümde çalışma boyunca kullanılacak olan bazı temel bilgilere yer verilmiştir. Üçüncü bölümde, önce karşılaştırılabilirlik çizgelerinin karelerinin karakterizasyonları verilerek ardından karşılaştırılabilirlik çizgelerinin karelerinin renklendirilmesi problemi incelenmiştir. Bu kapsamda, zayıf üçgensel iki-parçalı çizgeler, aralık sıralarının karşılaştırılabilirlik çizgeleri, boyutu 2 olan kısmi sıralı kümelerin karşılaştırılabilirlik çizgeleri, ağaç-benzeri ve üçgensel karşılaştırılabilirlik çizgelerinin karelerinin renklendirmeleri için üst sınırlar verilerek, yüksekliği 3 olan kısmi sıralı kümelerin karşılaştırılabilirlik çizgeleri ve zayıf üçgensel karşılaştırılabilirlik çizgelerinin karesel renklendirmesi için özel durumlar altında üst sınırlar elde edilmiştir. Son bölümde çeşitli genel çizge sınıflarının karesel renklendirilmesi problemi ele alınmıştır. Köşe sıralama karakterizasyonlarından faydalanılarak güçlü sıralanabilir, dual üçgensel, güçlü üçgensel, üçgensel ve ardıl-karşılaştırılabilirlik çizgelerinin karesel kromatik sayıları için üst sınırlar elde edilmiştir. Ayrıca aralık temsilleri yardımıyla aralık, ardıl-aralık, aralık kapsama (permütasyon) çizgeleri ve aralık k-çizgelerinin karelerinin kromatik sayıları için üst sınırlar verilmiştir.
In this thesis, characterization and coloring of the square of comparability graphs are studied. Square colorings of various general graph classes are further investigated. The main goal of this dissertation is to characterize squares of comparability graphs and provide tight upper bounds on the chromatic number of squares of comparability graphs and graphs which admit a vertex ordering characterization or an interval representation. This thesis consists of four chapters. First chapter presents a brief summary of literature, while the second chapter provides preliminary definitions and notations used throughout the study. In chapter three, we characterize squares of comparability graphs and provide upper bounds on the chromatic number of the squares of chordal bipartite graphs, comparability graphs of interval orders, treelike comparability graphs, chordal comparability graphs and comparability graphs of posets of dimension at most 2. We also give sufficient conditions on weakly chordal comparability graphs and the comparability graphs of posets of height 3, to have the desired upper bounds on their square coloring. In the final chapter, we deal with the coloring of squares of graphs which have a vertex ordering characterization or an interval representation. We establish upper bounds on the chromatic number of the square of strongly orderable, dually chordal, strongly chordal, chordal and cocomparability graphs, by appealing to their vertex ordering characterizations. We further provide upper bounds on the chromatic number of the squares of interval, co-interval, interval containment (permutation) and interval k-graphs by using their interval representations. Keywords: comparability graph, square of graph, coloring, square coloring, distance-2 coloring, vertex ordering, interval representation.