Çizgelerde yıldız renklendirme varyasyonları

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.