未解决问题，组合数学与离散数学，1943年提出

哈德维格猜想（图子式）

未解决

每个不含 $K_t$ 子式的无环图 $G$ 都是 $(t - 1)$ 可染色的；等价地说，每个染色数满足 $\chi(G) \ge t$ 的图 $G$ 都包含完全图 $K_t$ 作为图子式。

研究前沿截至2026年

截至2026年，哈德维格猜想在 $t \le 6$ 时已获证明，而对所有 $t \ge 7$ 仍未解决。即便是线性哈德维格猜想——即对所有无 $K_t$ 子式图 $G$ 有 $\chi(G) \le C t$ ——也依然悬而未决。继科斯托奇卡（1982）与托马森（1984）利用退化度证明 $\chi(G) = O(t \sqrt{\log t})$ 之后，诺林、波斯特尔与宋梓霞（2019/2023）突破了退化度屏障，随后德尔库尔与波斯特尔（2021）确立了目前最优的一般上界 $\chi(G) = O(t \log \log t)$ 。

已知最佳结果

哈德维格猜想对所有 $t \le 6$ 精确成立（罗伯逊、西摩与托马斯，1993）。
每个不含 $K_t$ 子式的图 $G$ 的染色数满足 $\chi(G) = O(t \log \log t)$ （德尔库尔与波斯特尔，2021，改进自诺林–波斯特尔–宋梓霞的结果）。

使用的方法及其局限

方法	取得的结果	局限所在
图子式结构理论与尖点图化归	将不含 $K_6$ 子式的极小 $6$ 色图刻画为平面图上的尖点图，从而将 $t = 6$ 化归为四色定理。	当 $t \ge 7$ 时，不含 $K_t$ 子式的图可由高亏格曲面与涡旋结构构造，不再受平面图染色定理的控制。
稠密子图连接与染色可分性分解	在高染色数图中提取顶点不相交的高连通稠密子图并将其连接成 $K_t$ 子式，从而导出 $\chi(G) = O(t \log \log t)$ 。	递归密度递增步骤在平衡小规模图界与构建 $K_t$ 所需的分块数量时，仍会损失一个 $\log \log t$ 因子。

尚未解决的问题

是否每个不含 $K_7$ 子式的图都是 $6$ 可染色的（ $t = 7$ ）？
是否存在绝对常数 $C > 0$ 使得每个不含 $K_t$ 子式的图 $G$ 均满足 $\chi(G) \le C t$ （线性哈德维格猜想）？

参考文献

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