12.6. Graf Renklendirme

Graf renklendirme, graf üzerinde birbirine komşu olan düğümlere farklı renk atama işlemidir; amaç, en az sayıda renk kullanılarak tüm düğümlere komşularından farklı birer renk vermektir. Renklendirmede kullanılan toplam renk sayısı kromatik (chromatik) sayı olarak adlandırılır.

Uygulamada, graf renklendirmenin kullanılacağı alanların başında, ilk akla gelen, harita üzerindeki bölgelerin renklendirilmesi olmasına karşın, graf renklendirme bilgisayar biliminde ve günlük yaşamdaki birçok problemin çözümüne ciddi bir yaklaşımdır.

Graf renklendirmede kullanılan algoritmalardan birisi Welch ve Powel'in önerdiği yöntemdir. Bu yöntem genel olarak düğümlerin derecelerine dayanmaktadır; düğüm dereceleri büyükten küçüğe doğru sıralanır ve en yüksek dereceli olana ilk renk atanır.

Dört Renk Teoremi (The Four Color Theorem)	Düzlemsel bir G=(D, K) grafı en fazla 4 renk kullanılarak renklendirilebilir; yani, kromatik sayı 4'tür.
İkiz Graf (Dual Graph)	Bir grafın ikizi, graf üzerindeki herbir kapalı alanın (bölgenin) birer düğümle temsil edilip komşu bölgelerin düğümleri arasına kenar eklenmesiyle elde edilen graftır. Yani bölge-düğüm dönüşümü yapılması işlemidir.