BỐN MÀU CHO MỌI BẢN ĐỒ, TÌM RA TRONG THỜI GIAN TUYẾN TÍNH

Mọi bản đồ vẽ trên một tờ giấy phẳng đều có thể được tô bằng bốn màu sao cho các nước láng giềng không bao giờ trùng màu. Francis Guthrie đưa ra giả thuyết này năm 1852; Appel và Haken chứng minh nó năm 1976. Nhưng định lý chỉ nói rằng bốn màu là tồn tại. Làm thế nào để tìm ra chúng cho một bản đồ cụ thể? «Không có câu trả lời dễ dàng», Yuta Inoue, thuộc Đại học Tokyo, cùng năm đồng nghiệp đến từ Nhật Bản, Canada, Slovenia và Đan Mạch viết. Vấn đề này rối rắm đến mức đã dẫn tới nhiều phản ví dụ được đề xuất.

Điểm, đường và tam giác

Mỗi quốc gia trở thành một điểm, hay đỉnh, và mỗi đường biên giới chung trở thành một đường, hay cạnh: bản đồ trở thành một đồ thị phẳng (planar graph), được vẽ mà không có đường nào cắt nhau. Tô màu nó nghĩa là gán cho mỗi đỉnh một trong bốn màu, sao cho hai đầu của mỗi cạnh khác màu nhau. Gọi n là số đỉnh. Chỉ cần xử lý các phép tam giác phân (triangulations), trong đó mọi mặt đều là tam giác: thêm cạnh chỉ khiến việc tô màu khó hơn.

Phép hoán đổi của Kempe

Nước đi cơ bản bắt nguồn từ một bài báo năm 1879 của A. B. Kempe. Ghép bốn màu thành cặp, chẳng hạn đỏ với xanh lam và xanh lục với vàng. Một xích Kempe (Kempe chain) là một nhóm đỉnh liên thông mang hai màu của cùng một cặp. Hoán đổi hai màu đó dọc theo cả một xích vẫn giữ cho cách tô màu hợp lệ.

Lấy một đỉnh v có bốn đỉnh kề, từ v0 đến v3 theo thứ tự quanh nó, và tô màu phần còn lại trước. Nếu các đỉnh kề dùng ba màu trở xuống, v nhận màu còn trống. Nếu chúng dùng cả bốn màu, hãy đi theo xích bắt đầu từ v0 mang các màu của v0 và v2. Nếu xích đó không chạm tới v2, hãy hoán đổi nó: v0 nhận màu của v2, giải phóng một màu cho v. Nếu nó có chạm tới v2, thì thay vào đó hãy hoán đổi xích của v1 mang các màu của v1 và v3, để v1 nhận màu của v3.

Những mảnh luôn có thể sửa chữa

Các chứng minh định lý dựa trên những cấu hình khả quy (reducible configurations): những mẫu nhỏ có thể cắt ra, rồi đặt trở lại sau khi phần còn lại đã được tô màu. Nếu màu của vành (ring) của chúng — những đỉnh nằm ngay xung quanh — không khớp, một số hữu hạn các phép thay đổi Kempe cải thiện được thực hiện bên ngoài luôn sửa được chúng: nhiều nhất là 25 với các mẫu được dùng ở đây, vốn có vành gồm nhiều nhất 18 đỉnh.

Một cấu hình khả quy (trái; mỗi con số là số đỉnh kề mà đỉnh đó phải có trong bản đồ đầy đủ) và cùng mẫu đó được bổ sung vành R của nó (phải). — Hình 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour và Thomas đã chỉ ra vào năm 1997 cách tô màu theo lối này, mỗi lần một mẫu. Mỗi vòng thu nhỏ đồ thị đi vài đỉnh và tốn một lượt duyệt toàn bộ đồ thị, nên thời gian là bậc hai: lâu gấp bốn lần với một bản đồ lớn gấp đôi.

Trong một bài báo trước đó (FOCS’26), chính sáu tác giả này đã chứng minh rằng mọi phép tam giác phân đều chứa một số cấu hình khả quy không chạm nhau tỷ lệ với n, lấy từ một danh sách gồm 8.202 mẫu — hoặc chừng ấy vòng ngắn có đỉnh ở cả hai bên, vốn cũng có ích. Họ gỡ bỏ tất cả các mẫu cùng một lúc, tô màu phần còn lại, rồi sửa chữa mọi vành cùng nhau. Một phép thay đổi Kempe ngẫu nhiên giúp ích cho một vành nhất định nếu nó chọn đúng cách ghép cặp màu (một cơ hội trên ba) và đúng mặt đồng xu được tung cho mỗi xích chạm vào vành (mỗi lần một cơ hội trên hai). Với tối đa 18 xích như vậy, đó là ít nhất một cơ hội trên 3 × 2¹⁸, tức 786.432: nhỏ, nhưng cố định. Vì thế số vòng chỉ tăng theo log n, xấp xỉ số lần có thể chia đôi n. Nhưng một phép thay đổi duy nhất có thể liên quan đến một phần không đổi của đồ thị: mỗi phép tốn một lượt duyệt toàn bộ, tổng cộng là n log n.

Một cái bảng thay cho một lượt duyệt

Bài báo mới giữ nguyên log n phép thay đổi nhưng làm cho mỗi phép rẻ hơn. Sau một bước chuẩn bị tốn thời gian tỷ lệ với n, mỗi phép thay đổi được tìm ra và thực hiện trong trung bình khoảng n / log n bước. Khi đó log n phép thay đổi cộng lại tốn thời gian tỷ lệ với n — thời gian tuyến tính — một cận mà các tác giả gọi là tối ưu.

Mẹo nằm ở «Phương pháp Bốn người Nga» (Method of Four Russians). Một bài toán con vừa vặn trong một mã ½ log n bit — một nửa số chữ số nhị phân cần để viết n — có nhiều nhất √n phiên bản khả dĩ, nên mọi lời giải của chúng có thể được tính trước và lưu vào một bảng. Chiếc máy tính được giả định, với các từ nhớ dài khoảng log n bit, đọc bất kỳ lời giải nào đã lưu chỉ trong một bước.

Đồ thị được cắt, lặp đi lặp lại, thành những vùng lồng nhau có đường biên ngắn. Những vùng nhỏ nhất chứa khoảng log n đỉnh và vừa vặn, kể cả màu sắc, trong một mã. Với mỗi vùng, một đồ thị tóm tắt nhỏ ghi lại những đỉnh biên nào cùng thuộc một xích Kempe. Khi đó một phép thay đổi truyền xuống dưới dạng các chuỗi bit «hoán đổi» hoặc «giữ nguyên», và trong mỗi vùng nhỏ, một lần tra bảng cập nhật mọi màu.

Một phần của đồ thị được tô bằng bốn màu. Vùng xám là một vùng R; các cạnh đen đậm thuộc về các xích Kempe của cặp đỏ-xanh lam và cặp xanh lục-vàng. — Hình 2, Inoue et al. (2026), arXiv:2610.39753.

Bản tóm tắt của cùng vùng đó: mỗi khối màu xanh đại diện cho một đoạn xích Kempe, và các đường của nó cho biết nó nối những đỉnh biên nào. — Hình 3, Inoue et al. (2026), arXiv:2610.39753.

Lựa chọn mà không cần gieo xúc xắc

Với các lựa chọn ngẫu nhiên, cách này đã tô màu một bản đồ trong thời gian tuyến tính tính trung bình. Loại bỏ xúc xắc mà không mất tốc độ là «phần khó khăn nhất, hơn hẳn mọi phần khác». Gọi một vành là còn sống chừng nào mọi quyết định cho đến lúc đó đều có lợi cho nó. Nếu u xích chưa được quyết định chạm vào nó được phó mặc cho việc tung đồng xu, nó sẽ sống sót với xác suất 1/2^u; cộng lại trên mọi vành còn sống, những con số này cho ra số vành sống sót kỳ vọng. Quyết định một xích làm tăng gấp đôi số hạng của mỗi vành muốn lựa chọn đó và đưa các số hạng khác về không. Thuật toán chọn phương án giữ cho tổng không giảm, để cuối cùng có ít nhất bằng ấy vành được giúp ích như may rủi trung bình lẽ ra đã giúp được.

Một cận, không phải một chiếc đồng hồ bấm giờ

Bài báo không báo cáo cách triển khai nào hay thời gian chạy nào, và các hằng số ẩn trong cụm từ «tỷ lệ với n» không được nêu ra. Chúng rất lớn: với mỗi mẫu trong 8.202 mẫu, thuật toán lưu số phép thay đổi cải thiện mà mọi cách tô màu vành của nó cần đến — «một lượng thông tin hằng số khổng lồ». Trong một phụ lục, họ cũng sửa «một lỗi nhỏ» trong một cách xây dựng vùng lồng nhau năm 2013 mà họ dựa vào. Một giả thuyết từ năm 1852 nay đi kèm với một quy trình tô màu có chi phí tăng không nhanh hơn chính tấm bản đồ mà nó tô.