MỘT AI ĐÁNH CHÌM GIẢ THUYẾT TÔ MÀU TỪ THẬP NIÊN 1990

Hãy lấy một mạng lưới gồm các điểm nối với nhau bằng các đường — một đồ thị. Một phép tô màu toàn phần (total colouring) gán một màu cho mọi điểm và mọi đường, tuân theo ba quy tắc: hai điểm kề nhau khác màu, hai đường gặp nhau tại một điểm khác màu, và một đường khác màu với hai điểm đầu mút của nó. Số màu nhỏ nhất làm được điều đó gọi là sắc số toàn phần, ký hiệu χ″(G).

Giờ hãy làm cho nó khó hơn. Cho mỗi điểm và mỗi đường danh sách riêng các màu được phép dùng, mọi danh sách có cùng kích thước k, và đòi hỏi một phép tô màu hợp lệ chọn từ các danh sách. Giá trị k nhỏ nhất làm được bất kể danh sách ra sao là sắc số toàn phần danh sách, χ″ℓ(G). Nó không bao giờ có thể nhỏ hơn χ″(G): nếu mọi danh sách giống hệt nhau, ta quay về bài toán thông thường.

Một giả thuyết từ cuối thập niên 1990

Ba nhóm — Borodin, Kostochka và Woodall; Juvan, Mohar và Škrekovski; Hilton và Johnson — đã độc lập đề xuất, vào cuối thập niên 1990, rằng danh sách riêng không bao giờ tốn thêm gì:

χ″ℓ(G) = χ″(G) với mọi đồ thị (kể cả khi có nhiều đường nối giữa hai điểm).

Đây là Giả thuyết tô màu toàn phần danh sách (List Total Colouring Conjecture). Các bằng chứng ủng hộ nó: nó đúng với các đồ thị mà không điểm nào có quá hai đường, và mọi đồ thị có đúng ba đường tại mỗi điểm (đồ thị chính quy bậc ba, cubic graph) đã được biết là cần tối đa 5 màu từ danh sách.

Phản ví dụ

Jonathan Noel, ở Đại học Victoria tại Canada, nay chỉ ra một đồ thị chính quy bậc ba có 20 điểm với χ″ = 4 nhưng χ″ℓ = 5. Giả thuyết đã sai.

Cách dựng rất gọn. Lấy bốn bản sao của một đồ thị nhỏ gọi là K₂,₃: hai điểm “riêng”, mỗi điểm nối với cùng ba điểm “đầu cuối”. Sau đó nối mỗi cặp bản sao bằng đúng một đường “chéo” giữa các điểm đầu cuối. Cuối cùng, mỗi điểm đều có ba đường.

Đồ thị G với một phép tô màu toàn phần chỉ dùng bốn màu, biểu thị bằng các hình và kiểu đường. — Hình 1, Noel (2026), arXiv:2609.38417.

Trong trò chơi thông thường, bốn màu là đủ: màu 4 dành cho mọi điểm riêng và mọi đường chéo, vốn không bao giờ chạm nhau, còn một bảng nhỏ và một quy tắc tuần hoàn lo phần còn lại.

Những danh sách không thể thỏa mãn

Cái bẫy dùng các màu từ 1 đến 5. Mọi điểm và đường của khối i nhận danh sách “mọi màu trừ i”; các đường chéo nhận những danh sách được chọn cẩn thận, thiếu màu 5 hoặc i + 2. Chứng minh sau đó diễn ra như một truyện trinh thám ngắn:

• Bổ đề: trong bất kỳ phép tô 4 màu nào của K₂,₃, hai điểm riêng phải cùng màu.
• Vậy mỗi khối i có một cặp màu {i, sᵢ}, và mỗi đường chéo giữa hai khối phải dùng một màu chung của cả hai cặp.
• Một chút đếm cho thấy phải có một màu t thuộc cả bốn cặp.
• Với mọi giá trị t có thể, có một đường chéo cụ thể mà danh sách của nó thiếu đúng màu đó. Mâu thuẫn.

Cách gán danh sách: mỗi điểm và đường có thể dùng mọi màu từ 1 đến 5 trừ màu được chỉ ra. Không phép tô màu toàn phần nào tôn trọng được các danh sách này. — Hình 2, Noel (2026), arXiv:2609.38417.

Máy tìm ra, nhà toán học kiểm chứng

Bài báo thẳng thắn một cách khác thường về nguồn gốc của nó. Ngày 24 tháng 9 năm 2026, Noel đã yêu cầu ChatGPT 6 Astra Ultra bác bỏ giả thuyết, và nó đã đưa ra phản ví dụ, “với rất ít đóng góp từ tác giả”. Ông kiểm tra các lập luận và viết lại văn bản từ các bản nháp do mô hình tạo ra; mô hình cũng giúp đọc soát, gợi ý tài liệu tham khảo và vẽ các hình. “Tác giả chịu hoàn toàn trách nhiệm về tính đúng đắn,” lời tuyên bố kết thúc. Bài báo là một bản tiền ấn phẩm, nhưng chứng minh đủ ngắn để bất kỳ độc giả kiên nhẫn nào cũng có thể kiểm chứng.

Chênh một, hay nhiều hơn?

Danh sách riêng có thể đòi thêm một màu. Liệu chúng có thể đòi thêm nhiều hơn? Một khoảng chênh bằng ba cũng sẽ lật đổ một giả thuyết họ hàng đã được nghiên cứu kỹ, Giả thuyết tô màu cạnh danh sách, vì χ″ℓ ≤ χ′ℓ + 2 và χ″ ≥ χ′. Noel khép lại bằng một câu hỏi mở mà phản ví dụ của AI vẫn để ngỏ: liệu χ″ℓ(G) ≤ χ″(G) + 1 với mọi đồ thị?