Komşular hep farklı renkte olsun diye her harita için dört renk yeter. Bu 1976'da kanıtlandı. Peki renkler gerçekte nasıl bulunur?
Klasik araç Kempe zinciridir. İki renk seçin ve yalnızca bu ikisiyle boyanmış, birbirine bağlı ülke öbeğinin tamamını alın. Öbeğin her yerinde iki rengin yerini değiştirin: harita doğru boyanmış olarak kalır.
Sorun şu: tek bir değiş tokuş bütün haritaya yayılabilir. Önceki rekor, haritalar büyüdükçe daha fazla değiş tokuş gerektiriyordu. Her biri haritanın baştan sona taranmasına mal oluyordu.
Tokyo'dan Kopenhag'a altı matematikçi bu ek maliyeti ortadan kaldırdı. Algoritmaları n ülkeyi n ile orantılı bir sürede boyuyor. Haritanın küçük parçaları bir kez çözülüyor, tablolarda saklanıyor, sonra yalnızca bakılıyor. Yazarlar bu hızın optimal olduğunu söylüyor.
Kaynak: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










