Empat warna cukup untuk peta apa pun, sehingga negara-negara yang bertetangga selalu berbeda warna. Hal itu terbukti pada 1976. Tetapi bagaimana sebenarnya menemukan warna-warnanya?
Alat klasiknya adalah rantai Kempe. Pilih dua warna. Ambil seluruh gugus negara yang tersambung dan hanya memakai kedua warna itu. Tukar keduanya di seluruh gugus itu: peta tetap terwarnai dengan benar.
Masalahnya: satu penukaran saja bisa merambat ke seluruh peta. Rekor sebelumnya membutuhkan lebih banyak penukaran seiring membesarnya peta. Setiap penukaran menuntut satu kali penelusuran penuh atas peta.
Enam matematikawan, dari Tokyo hingga Kopenhagen, telah menghapus biaya tambahan itu. Algoritma mereka mewarnai n negara dalam waktu yang sebanding dengan n. Potongan-potongan kecil peta diselesaikan sekali, disimpan dalam tabel, lalu cukup dicari. Para penulis menyebut kecepatan ini optimal.
Sumber: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










