Erdős 问题 #1032

问题

We say that a graph is $4$ -chromatic critical if it has chromatic number $4$ , and removing any edge decreases the chromatic number to $3$ .

Is there, for arbitrarily large $n$ , a $4$ -chromatic critical graph on $n$ vertices with minimum degree $\gg n$ ?

问题陈述引自 erdosproblems.com/1032（Thomas Bloom 维护），保留英文原文。原始出处：[Er93,p.341][Va99,3.60]。该网站上的当前状态：未解决。

AI 贡献

以下记录来自 Terence Tao 的 Wiki AI contributions to Erdős problems（数据截至 2026 年 6 月 30 日）。🟢 完整、🟡 部分、⚪ 待核实、🔴 有误。

日期	类型	AI 系统	结果	相关文献
7 May, 2026	AI 在已知文献基础上完成	Codex, GPT-5.5 Pro	🟡 Improved partial result（Lean 形式化）	🟡 Luo, Ma, and Yang (2023)

说明

Wiki 中的分类是暂定的，也不是一份评测榜单。许多 Erdős 问题从未有过完整的文献调研，看似新的结果日后可能被发现早已存在；也有一些问题本身的表述有歧义或错误。完整的讨论见问题页面。

∎