EMPAT WARNA UNTUK PETA APA PUN, DITEMUKAN DALAM WAKTU LINEAR

Peta apa pun yang digambar di atas selembar kertas datar dapat diwarnai dengan empat warna sehingga negara-negara yang bertetangga tidak pernah berbagi warna. Francis Guthrie mengajukannya sebagai dugaan pada 1852; Appel dan Haken membuktikannya pada 1976. Tetapi teorema itu hanya menyatakan bahwa empat warna tersebut ada. Bagaimana menemukannya untuk peta tertentu? “Tidak ada jawaban yang mudah,” tulis Yuta Inoue, dari University of Tokyo, dan lima koleganya dari Jepang, Kanada, Slovenia, dan Denmark. Soal ini begitu rumit sehingga memunculkan banyak usulan contoh penyangkal.

Titik, garis, dan segitiga

Setiap negara menjadi sebuah titik, atau simpul (vertex), dan setiap perbatasan bersama menjadi sebuah garis, atau sisi (edge): peta berubah menjadi graf planar, yang digambar tanpa garis yang bersilangan. Mewarnainya berarti memberi setiap simpul satu dari empat warna, berbeda di kedua ujung setiap sisi. Sebut n sebagai jumlah simpul. Cukup menangani triangulasi, yaitu graf yang setiap mukanya berupa segitiga: sisi tambahan hanya membuat pewarnaan makin sulit.

Penukaran Kempe

Langkah dasarnya berasal dari makalah tahun 1879 karya A. B. Kempe. Pasangkan keempat warna, misalnya merah dengan biru dan hijau dengan kuning. Rantai Kempe adalah sekelompok simpul yang terhubung dan memakai dua warna dari satu pasangan. Menukar kedua warna itu di sepanjang satu rantai utuh menjaga pewarnaan tetap sah.

Ambil sebuah simpul v dengan empat tetangga, v0 hingga v3 secara berurutan di sekelilingnya, dan warnai sisanya terlebih dahulu. Jika para tetangga memakai tiga warna atau kurang, v mengambil warna yang tersisa. Jika mereka memakai keempatnya, ikuti rantai yang bermula di v0 dalam warna v0 dan v2. Jika rantai itu tidak mencapai v2, tukarlah: v0 mengambil warna v2, sehingga membebaskan satu warna untuk v. Jika rantai itu mencapai v2, tukarlah sebagai gantinya rantai v1 dalam warna v1 dan v3, sehingga v1 mengambil warna v3.

Potongan yang selalu dapat diperbaiki

Bukti-bukti teorema ini bertumpu pada konfigurasi tereduksi (reducible configurations): pola-pola kecil yang dapat dipotong keluar, lalu dipasang kembali setelah sisanya diwarnai. Jika warna-warna cincin-nya — simpul-simpul tepat di sekelilingnya — tidak cocok, sejumlah terbatas perubahan Kempe yang memperbaiki, dilakukan di luar, selalu dapat membereskannya: paling banyak 25 untuk pola-pola yang dipakai di sini, yang cincinnya memiliki paling banyak 18 simpul.

Sebuah konfigurasi tereduksi (kiri; setiap angka menunjukkan berapa banyak tetangga yang harus dimiliki simpul itu dalam peta lengkap) dan pola yang sama dilengkapi dengan cincinnya R (kanan). — Gambar 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour, dan Thomas menunjukkan pada 1997 cara mewarnai dengan metode ini, satu pola pada satu waktu. Setiap putaran mengecilkan graf beberapa simpul dan menuntut satu penelusuran atas seluruh graf, sehingga waktunya kuadratik: empat kali lebih lama untuk peta yang dua kali lebih besar.

Dalam makalah sebelumnya (FOCS’26), keenam penulis yang sama membuktikan bahwa setiap triangulasi memuat sejumlah konfigurasi tereduksi yang tidak saling bersentuhan sebanding dengan n, yang diambil dari daftar berisi 8.202 pola — atau sama banyaknya lingkaran pendek dengan simpul di kedua sisinya, yang juga membantu. Mereka menyingkirkan semua pola sekaligus, mewarnai sisanya, lalu memperbaiki semua cincin bersama-sama. Sebuah perubahan Kempe acak membantu cincin tertentu jika ia memilih pasangan warna yang tepat (satu peluang dari tiga) dan lemparan koin yang tepat pada setiap rantai yang menyentuh cincin itu (masing-masing satu peluang dari dua). Dengan paling banyak 18 rantai semacam itu, peluangnya setidaknya satu dari 3 × 2¹⁸, atau 786.432: kecil, tetapi tetap. Jadi, jumlah putaran hanya tumbuh sebesar log n, kira-kira berapa kali n dapat dibagi dua. Tetapi satu perubahan saja dapat melibatkan sebagian tetap dari graf: masing-masing menuntut satu penelusuran penuh, total n log n.

Sebuah tabel alih-alih penelusuran

Makalah baru ini mempertahankan log n perubahan tetapi membuat setiap perubahan lebih murah. Setelah persiapan yang memakan waktu sebanding dengan n, setiap perubahan ditemukan dan dijalankan dalam rata-rata sekitar n / log n langkah. Bersama-sama, log n perubahan itu lalu memakan waktu sebanding dengan n — waktu linear — sebuah batas yang oleh para penulis disebut optimal.

Triknya adalah “Metode Empat Orang Rusia” (Method of Four Russians). Sebuah subsoal yang muat dalam kode sepanjang ½ log n bit — setengah dari jumlah digit biner yang diperlukan untuk menuliskan n — memiliki paling banyak √n versi yang mungkin, sehingga semua jawabannya dapat dihitung terlebih dahulu dan disimpan dalam tabel. Komputer yang diasumsikan, dengan kata memori sekitar log n bit, membaca jawaban tersimpan mana pun dalam satu langkah.

Graf itu dipotong, lagi dan lagi, menjadi wilayah-wilayah bersarang dengan perbatasan pendek. Wilayah terkecil memuat sekitar log n simpul dan muat, termasuk warnanya, dalam satu kode. Untuk setiap wilayah, sebuah graf ringkasan kecil mencatat simpul perbatasan mana yang berbagi satu rantai Kempe. Sebuah perubahan lalu turun sebagai untaian bit “tukar” atau “biarkan”, dan di setiap wilayah kecil satu kali pencarian memperbarui setiap warna.

Bagian dari sebuah graf yang diwarnai dengan empat warna. Area abu-abu adalah wilayah R; sisi-sisi hitam tebal termasuk dalam rantai Kempe pasangan merah-biru dan hijau-kuning. — Gambar 2, Inoue et al. (2026), arXiv:2610.39753.

Ringkasan wilayah yang sama: setiap gumpalan biru mewakili sepotong rantai Kempe, dan garis-garisnya menunjukkan simpul perbatasan mana yang dihubungkannya. — Gambar 3, Inoue et al. (2026), arXiv:2610.39753.

Memilih tanpa dadu

Dengan pilihan acak, cara ini sudah mewarnai sebuah peta dalam waktu linear secara rata-rata. Menyingkirkan dadu tanpa kehilangan kecepatan adalah “sejauh ini bagian yang paling menantang”. Sebut sebuah cincin hidup selama setiap keputusan sejauh ini menguntungkannya. Jika u rantai yang belum diputuskan dan menyentuhnya diserahkan pada lemparan koin, cincin itu akan bertahan dengan probabilitas 1/2^u; dijumlahkan atas semua cincin yang hidup, angka-angka ini memberikan jumlah harapan cincin yang bertahan. Memutuskan sebuah rantai menggandakan suku setiap cincin yang menginginkan pilihan itu dan membuat nol suku cincin lainnya. Algoritma itu mengambil opsi yang menjaga jumlahnya agar tidak turun, sehingga pada akhirnya cincin yang terbantu setidaknya sebanyak yang akan terbantu oleh kebetulan secara rata-rata.

Sebuah batas, bukan stopwatch

Makalah ini tidak melaporkan implementasi maupun waktu eksekusi, dan konstanta yang tersembunyi dalam “sebanding dengan n” tidak diberikan. Konstanta itu besar: untuk setiap pola dari 8.202 pola, algoritma menyimpan berapa banyak perubahan perbaikan yang dibutuhkan setiap pewarnaan cincinnya — “sejumlah informasi konstan yang sangat besar”. Dalam sebuah lampiran, mereka juga memperbaiki “sebuah kesalahan kecil” dalam konstruksi wilayah bersarang tahun 2013 yang menjadi landasan mereka. Sebuah dugaan dari 1852 kini disertai prosedur pewarnaan yang biayanya tumbuh tidak lebih cepat daripada peta yang diwarnainya.