Bốn màu là đủ cho mọi bản đồ, sao cho các nước láng giềng luôn khác màu nhau. Điều đó đã được chứng minh năm 1976. Nhưng làm thế nào để thực sự tìm ra cách tô màu?
Công cụ kinh điển là xích Kempe. Chọn hai màu và lấy trọn mảng liên thông các nước chỉ tô bằng hai màu đó. Hoán đổi chúng trên toàn bộ mảng: bản đồ vẫn được tô màu đúng.
Vấn đề là: chỉ một lần hoán đổi có thể lan ra khắp bản đồ. Kỷ lục trước đây cần nhiều lần hoán đổi hơn khi bản đồ lớn lên. Mỗi lần lại tốn một lượt duyệt toàn bộ bản đồ.
Sáu nhà toán học, từ Tokyo đến Copenhagen, đã loại bỏ chi phí phụ trội đó. Thuật toán của họ tô màu n quốc gia trong thời gian tỷ lệ với n. Các mảnh nhỏ của bản đồ được giải một lần, lưu vào bảng, rồi chỉ cần tra cứu. Các tác giả gọi tốc độ này là tối ưu.
Nguồn: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










