Kenar-renklendirme problemine giriş

Bu tezde çalışılan graf kenar renklendirme problemi temel olarak; bir grafın bütün kenarlarını, grafın birbirine komşu iki kenarının farklı renklerde olacak şekilde renklendirilmesi esasına dayanmaktadır. Buradaki zorluk, bir grafın böylesi bir kenar renklendirilmesinin elde edilebilmesi için gereken minimum sayıda rengin bulunmasıdır. Bir $G$ grafı için ihtiyaç duyulan minimum sayıda renge, bu grafın "kromatik indeksi" denir ve tüm tez boyunca $\chi'(G)$ olarak gösterilmiştir. Bu tezin ilk bölümü, graflarla, alt graflarla, graflardaki bağlantılılık kavramıyla, graflardaki eşleştirme ve faktörizasyon kavramlarıyla ilgili temel tanımların verildiği, bir graf teoriye giriş bölümüdür. İkinci bölüm, bizim esas konumuz olan graf kenar renklendirme ile ilgilidir. Bu bölümde, $\chi'$ parametresini yorumlamak için birden fazla yol verilmiş, $\chi'$ parametresi için üst ve alt sınırlar bulmak ile ilgili önemli çeşitli teoremler ifade ve ispat edilmiştir. Ayrıca, ikinci bölümde, sınıflandırma problemine giriş yapılmıştır. Bu bölümü, (dairesel kenar renklendirme, liste kenar renklendirme ve toplam renklendirme gibi) bazı çeşitli renklendirme konularına değinerek sonlandırdık. Bu tezin üçüncü ve son bölümü, etkin bir şekilde çalışan renklendirme algoritmalarının araştırılmasına ve geliştirilmesine yardımcı olan bazı ana sonuçların, bazı önemli teoremlerin ve varsayımların ifadelerinin bir incelemesi ve açıklamasıdır. Bu algoritmaların geliştirilmesi, kolay bir iş olmayan grafların kromatik indeksinin belirlenmesinde çok büyük bir adımdır.