Bài toán mở, Tổ hợp và Toán rời rạc, nêu năm 1943

Giả thuyết Hadwiger (minors đồ thị)

Còn mở

Mọi đồ thị không khuyên $G$ không chứa minor $K_t$ đều tô được bằng $(t - 1)$ màu; tương đương, mọi đồ thị $G$ có sắc số $\chi(G) \ge t$ đều chứa đồ thị đầy đủ $K_t$ làm một minor.

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giả thuyết Hadwiger đã được chứng minh cho $t \le 6$ và còn mở với mọi $t \ge 7$ . Ngay cả giả thuyết Hadwiger tuyến tính — rằng $\chi(G) \le C t$ với mọi đồ thị $G$ không có minor $K_t$ — vẫn chưa được giải quyết. Sau khi Kostochka (1982) và Thomason (1984) chứng minh tính suy biến cho $\chi(G) = O(t \sqrt{\log t})$ , Norin, Postle và Song (2019/2023) đã phá vỡ rào cản suy biến, rồi Delcourt và Postle (2021) thiết lập cận tổng quát tốt nhất hiện nay $\chi(G) = O(t \log \log t)$ .

Kết quả tốt nhất đã biết

Giả thuyết Hadwiger đúng chính xác cho mọi $t \le 6$ (Robertson, Seymour và Thomas, 1993).
Mọi đồ thị $G$ không chứa minor $K_t$ đều có sắc số $\chi(G) = O(t \log \log t)$ (Delcourt và Postle, 2021, cải thiện kết quả của Norin–Postle–Song).

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Lý thuyết cấu trúc minor đồ thị và quy giản đỉnh chóp	Phân loại các đồ thị tối tiểu sắc số $6$ không có minor $K_6$ thành các đồ thị đỉnh chóp trên đồ thị phẳng, quy trường hợp $t = 6$ về định lý bốn màu.	Với $t \ge 7$ , các đồ thị không có minor $K_t$ có thể được tạo thành từ các mặt giống cao và các xoáy không còn kiểm soát được bằng các định lý tô màu phẳng.
Kỹ thuật nối đồ thị con dày đặc và phân rã tách sắc số	Trích xuất các đồ thị con dày đặc liên thông cao rời nhau theo đỉnh trong đồ thị sắc số lớn rồi nối chúng thành minor $K_t$ , thu được $\chi(G) = O(t \log \log t)$ .	Các bước tăng mật độ đệ quy vẫn mất một nhân tử $\log \log t$ khi cân bằng cận của các đồ thị nhỏ với số mảnh cần thiết để ghép thành $K_t$ .

Câu hỏi còn mở

Liệu mọi đồ thị không có minor $K_7$ có đều tô được bằng $6$ màu ( $t = 7$ ) hay không?
Có tồn tại hằng số tuyệt đối $C > 0$ sao cho mọi đồ thị $G$ không có minor $K_t$ đều thỏa mãn $\chi(G) \le C t$ (giả thuyết Hadwiger tuyến tính) hay không?

Tài liệu tham khảo

Neil Robertson, Paul Seymour, Robin Thomas (1993). Hadwiger's conjecture for K6-free graphs · DOI:10.1007/BF01202354
Sergey Norin, Luke Postle, Zi-Xia Song (2023). Breaking the degeneracy barrier for coloring graphs with no Kt minor · DOI:10.1016/j.aim.2023.108959 · arXiv:1910.09378