Variations of star coloring on graphs

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Hacettepe Üniversitesi, Fen Bilimleri Enstitüsü, MATEMATİK ANABİLİM DALI, Türkiye

Tezin Onay Tarihi: 2021

Tezin Dili: İngilizce

Öğrenci: ALAİTTİN KIRTIŞOĞLU

Asıl Danışman (Eş Danışmanlı Tezler İçin): Selma Altinok Bhupal

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu tez, beş bölümden oluşup çeşitli boyama türlerine odaklanmaktadır. Giriş bölümünden sonra, ikinci bölümde çalışma boyunca kullanılan temel tanımlar ve metodlar tanıtılır. Üçüncü bölümde, sırasıyla iki renkli döngüleri ve yolları yasaklayan döngüsüz ve yıldız boyama üzerine literatürdeki bazı çalışmalar sunulmaktadır. Tekrar etmeyen ve k-mesafeli boyamalar, yıldız boyamayla yakında ilişkili olduğu için, yıldız boyamaya bir bakış açısı kazandırmak adına bu bölümde tartışılır. Bir $G$ çizgesinde $P_k$-boyama, komşu köşelerin farklı renklere sahip olduğu bir boyamadır ve çizgedeki $k$ köşeye sahip yolların iki renkli olmasını yasaklar. Dördüncü bölüm, yolların ve döngülerin çarpımları olan silindir, 2 boyutlu kafes ve tori gibi çizge çarpımlarına ayrılmıştır. Bu bölümde, bu çizge ailelerinin $P_k$-kromatik sayıları $k=5,6$ için tam olarak belirlenir. Olasılıksal yöntem, istenen bir objeyi rastgele inşa ederek, objenin varlığının pozitif olasılığa sahip olduğunu göstermek için kullanılan temel bir araçtır. Beşinci bölümde, herhangi bir çizgenin $P_k$-kromatik sayısına yönelik genelleştirilmiş sınırlar bulunmuştur. Benzeri sınırlar, iki renkli bazı döngüleri içermeyen çizgeler için elde edilmiştir.