图论中的 50 个公开问题

R(5,5) 介于 43 与 48 之间，精确值未知。

现状爱多士说「让外星文明来算 R(5,5)：一年内可以；R(6,6)：一百年也不够」。R(4,5)=25 于 1995 年确定后，R(5,5) 成为已知上界—下界间隙中最著名的数值。爱多士悬赏 250 美元至今无人领取。

已知 R(3,8)=28、R(3,9)∈[36,? ]；对一般 t，R(3,t) 的精确值只在 t≤10 内基本确定。

现状Kim 1995 证明 R(3,t) ~ t²/log t（解开了 90 年的渐近阶之谜），但常数项与有限具体值之间隔着整个「极值组合有限检查」的鸿沟——而检查本身已达组合爆炸。

R(k,k) 是否渐近于 4^k/k 的某个幂次修正？指数 1/2（Erdős–Szekeres 下界与 Erdős 上界之间）能否精确到多项式水平？

现状2019 年以来 Campos–Griffiths–Morris–Sahasrabudhe 把上界降到 (4−ε)^k（ε 约 10⁻⁵），是 80 年来首次实质突破；但与下界 4^k/k²（指数 2）之间仍有深渊。

四色三角形拉姆齐数 R₄(3) 介于 51 与 62 之间，精确值未知。

现状R₃(3)=17（1968 年确定）之后，R₄(3) 五十多年原地踏步。相关工作（Radziszowski 的动态综述）记录了大量部分结果，连计算机穷举都因搜索空间过大而失效。

ex(n, K_s,t) 的精确指数是否为 1−1/max(s,t)？K_3,3、C₄ 的精确渐近常数是多少？

现状Kővári–Sós–Turán 给出上界，极性构造给出匹配下界（当 t∈{2,3} 或 s=2 时），一般情形连阶都不知道；C₈ 型图是否存在更差的指数（superlinear gap）是近年核心悬念。

任何二部图的「同态密度」不小于随机同构二部图的密度：对任意图 H 与任意图 G，同态密度 t(H,G) ≥ t(K₂,G)^e(H)（H 为二部图）。

现状对「镜像树」、偶圈、完全二部图、树及其大量组合已证；一般情形是极值图论与图极限（图隆）理论的接口问题，被视为「图论的 Szemerédi 正则性试金石」。

在 3-均匀超图（三元组集）中，每个 4 顶点至多张 3 条超边时，超边总数的渐近最大值是多少？图兰猜想答案为 (5/9)·C(n,3)。

现状自 1940 年图兰提出，他的「极性构造」给出匹配 (5/9)·C(n,3) 的下界候选，但其最优性至今未证；Füredi 等的稳定性结果把问题压缩到「极性构造附近」却不能完工。它是「多项式方法失效区」的标志性案例。

对每个 k，存在 n₀ 使任何三均匀超图若每 k 个顶点至多张 1 条边且总边数 ≥ εn²，就含一个 ℓ-圈（特定局部模式）。

现状著名的 (6,3) 情形（每 6 顶点至多 2 条超边）近年已取得决定性渐近突破，若干其他参数亦被锁定；但一般 k、一般 ℓ 的完整图景仍开。它是加法组合与超图极值理论的交叉路标。

若一个 n 顶点图的团数与独立数都至多为 n^1−ε，则它含有 n^δ 个顶点的诱导同构拷贝（δ 只依赖 ε）。

现状对无诱导 C₅、半完美图、有序图等有大量 δ>0 的特殊结果（Bousquet–Lagoutte–Thomassé、Scott–Seymour–Spirkl 等）；一般形式被称为「结构图论最想要的单一定理」。

对参数 2≤p<q，函数 f(n,p,q)（n 顶点图中最少边数使得每个 p-顶点子图至多 q 条边可避免）的渐近阶何时为线性、n^3/2 还是 n^2−δ？

现状(p,q)=(3,3) 线性、(4,5) 平方已定；大量区间（如 (4,4)、(5,6) 的精确阶）仍未定，Ma–Yang 等近年推进了几个格子。这个「格子地图」是极值组合的活地图。

每个 k-染色需要 ≥ k 种颜色的图都包含 K_k 的图子式。

现状k≤6 已证（k=6 由 Kawarabayashi–Song 2014 完成）；k≥7 的任何一般进展都依赖图子式理论的重炮却仍无突破。四色定理是 k=5 的特例（Hadwiger 1943 提出时即观察到）。

对任意森林 T，不含诱导拷贝 T 的图类的染色数被只依赖 T 的函数有界。

现状即「无诱导森林 T 的图是 χ-有界的」。对星形、P₅、P₆ 等已证；一般森林（即使 P₇）仍开。它是 χ-有界理论的基石猜想之一。

平面的染色数（等距单位距离图的色数）究竟取 5、6 还是 7？

现状2018 年 de Grey 构造出 1581 个顶点的单位距离图需 5 色，终结了 68 年的「≤4」猜想；下界 5、上界 7 之间的 6 仍未定。已有构造缩到约 500 顶点，距 6 或 7 的判定还很远。

把平面点对按「距离为奇数」连边（奇距离图）需要多少种颜色？

现状奇圈图说明至少 3 色；Arman–Tsaturian 与 Pach 等证明其染色数随尺寸增长（无界），但无显式下界序列。这是「度量约束染色」家族中最空白的成员。

任何简单图的全染色数（点+边同染）不超过最大度 Δ+2。

现状1965 年提出。已知对 Δ 很大的一般图与多数图类成立（概率方法+熵压缩）；整体上界最好为 Δ+O(log Δ·(log log Δ)⁷)（Molloy–Reed 系），最后一步恒等式仍未跨过。

多重图的列表边染色数等于其边染色数（χ′_L(G) = χ′(G)）。

现状对二部多重图（Galvin 定理）与完全图等已证；一般多重图连 Δ+1 附近的列表版本都未证。它与「列表着色等于着色」的整体哲学——组合征兵、Polymath12 等方法——交织在一起。

没有三角形与四边形的平面图（围长 ≥5）是否都可 3 着色？

现状格勒茨施定理（围长 ≥4 三角剖分 3 可着色）与围长 5 的强 3 染色部分结果之间存在缺口；Steinberg 猜想（围长 ≥5 ⇒ 4 可着色）已于 2017 年被否证，但 3 可着色版仍在。

每个平面图是否都可在「每个顶点给定 4 种颜色的列表」下正常染色？

现状Thomassen 证明平面图 5 可选（1994），4 可选问题至今未决；4 列表即「四色定理的列表加强版」。已知反例只在 5 列表以下出现，4 是分水岭。

平面图的平方图（距离 ≤2 的点连边）染色数的确切函数 f(Δ) 是多少？Wegner 猜想的修正版 f(Δ)≤Δ+5 是否成立？

现状Wegner 1977 的原始 Δ+4 猜想已有反例（Δ=3 时的 7 色需求与 Molloy–Salavatian 的构造）；Molloy–Reed 给出 1.66Δ^3/2，后改进至 Δ+O(Δ^2/3log Δ) 等，但 Δ+O(1) 都未证。

每个 ≥3 顶点的图都由它的「顶点删除卡片集」（所有 n−1 顶点导出子图的同构类）唯一决定。

现状凯利–乌拉姆 1941 年提出，被誉为「图论最重要的未解问题」。边删除版本（边重构）对 3 正则图等已证；一般情形只有零星不变量（特征多项式、连通性）可恢复。

每个 1-韧度图（删除任意非空集合 S 后剩余分支数 ≤ |S|）都含哈密顿圈。

现状Chvátal 1973 年提出，同时证明哈密顿图必 1-韧（反向即本猜想）。已知最好反例搜索仍空白，韧度 0.9 的图不哈密顿的构造存在；它是「哈密顿性充分条件」的头号目标。

每个 3 连通、3 正则、二部的平面图都有哈密顿圈。

现状1969 年提出。塔特已证 4 连通平面图哈密顿；Barnette 剪去一条连通度。若为真，可给出四色定理的全新证明思路。目前验证到几千个顶点的构造类，无任何证明路径。

每个无桥图都有一个处处非零的 3-流（即边可定向赋权使每点流量守恒、权重非零且在 ℤ/3 中）。

现状塔特 1972 年提出；4-流版本对皮特森图子式禁图已证。Thomassen 把 3-流化归到 5 连通图；Lovász 等的分解方法推进到 6-流。它是对偶于「围长与染色」的整数流纲领核心。

每个无桥、非皮特森型的图都有处处非零的 4-流（等价地：不含皮特森图子式的无桥图可 4-边染色的定向版）。

现状比 3-流弱、比五流定理强。已知对无 K_3,3/皮特森子式的图与 4-边连通图成立。皮特森图这个「最小非哈密顿三次图」的幽灵盘踞在整个流理论中。

每个无桥图都有一个「每条边恰好出现在两个圈中」的圈族。

现状塔特纲领的核心（1970s 提出）。与 4-流、嵌入曲面（双覆盖 ⇔ 可定向双面嵌入）等价链条众多；Szekeres 悬赏 $10,000。平面图由欧拉公式立得，一般图的最小反例 hunt 进行了五十年。

每个连通顶点传递图都有哈密顿路（圈只在少数例外中缺失）。

现状1969 年提出；已知反例只有 5 个（皮特森图、考克斯特图等），且都没有哈密顿圈但有哈密顿路。「这 5 个例外之外全有圈」是加强版猜想。凯莱图情形已有大量正结果。

每个有限群的每个连通凯莱图都有哈密顿圈。

现状交换群已由 Chen–Quimpo 定理解决（1976）；一般群（包括洛瓦兹提出的均匀呈现型）仍未解决。它与「群与图同构的算法」（Babai 准多项式 GI）共同构成凯莱图理论两大开放前沿。

每个 2n−2 个顶点的竞赛图都包含任意给定的 n 个顶点的有向树。

现状1971 年提出。Bucić–Letzter–Sudakov 证明近似版（2n+o(n)），并覆盖大量树型（Q-树等）；精确常数 2 的最后一步未跨。它是「有向树普遍存在性」的末端问题。

每个「套扣图」（每条边与其他边恰交一次的直线段图）的边数不超过顶点数。

现状Conway 悬赏 $1000 征求证明或反例。已证边数至多约 1.4n（多次改进），距 n 尚有一步；「每边恰交一次」的极端约束下没人能构造出超过 n 条边的例子。

每棵树都有一个「优美标号」：顶点标 0…n 使边标（差）两两不同。

现状1967 年提出；「优美标号」能给出 K_2n+1 的树分解（Ringel 猜想——2020 年已被 Montgomery 等证明）。但逐树优美标号本身仍未解决，连「所有直径 ≤5 的树优美」都曾长期悬置。它被誉为「树上的四色定理」。

K_n 的直线交叉数（顶点凸位置）的确切公式是什么？已知到 n=27 为止。

现状Ábrego–Fernández-Merchant 给出下界、 fabila 的构造给出候选；「跨数」的多项式不变量（如 ≤3-交叉的计数）是目前唯一系统工具。n≥28 之后的精确值需要全新的「交叉计数代数」。

n 个平面点最多产生多少对单位距离？渐近主导项是多少？

现状爱多士 1946 年下界 n^{1+c/log log n}（整数格构造）与 Spencer–Szemerédi–Trotter 上界 n^4/3 之间八十余年无进展。连「是否存在 n^1+ε 构造」都未决。组合几何的大半工具箱（交叉引理、多项式方法）都为它而生。

是否存在一个 99 个顶点的图：每个顶点度为 10、直径 2、围长 3、且删去任一点后仍直径 2？

现状Conway 悬赏 $1000（他造出 96 顶点的近似品后提出）。Moore 图理论与「degree/diameter 问题」的标志性缺口；计算机搜索已被对称性约束大幅压缩但仍未穷尽。

使任意点集必含 7 边凸多边形所需的最少点数 ES(7) 是多少？已知 33≤ES(7)。

现状ES(5)=9 曾悬置 35 年（2006 年计算机解决），ES(6)=17 于 2016 年被 Suk 连同渐近 ES(k)=2^k+o(k) 一并证得；ES(7) 起的精确值完全开放。「渐近之后」的有限组合成为离散几何的新战场。

把 K_n 分解成最少几层平面子图？θ(K_n) 的确切公式未知。

现状已知 ⌈(n+7)/6⌉ ≤ θ ≤ ⌈(n+2)/6⌉ 型夹逼（Beineke–Harary 与 Vasudevan 系）；n mod 6 的多数剩余类已锁定，少数类与精确公式仍开。「层」与「书厚度（pagenumber）」的平行问题同样半开。

每条边至多交叉一次的图（1-平面图）是否都 5 可着色？（6 可着色已证）

现状Borodin 证明 1-平面图 6 可着色；5 的下界由构造达到。「5 可着色」若成立将统一平面图与 1-平面图的染色光谱；目前的障碍是交叉点附近的局部结构太多。

判定两个图是否同构（GI）是否存在多项式时间算法？

现状Babai 2015 证明准多项式时间（exp((log n)^O(1))），终结了 Luks 时代；GI 既未被证明 NP 完全（多数复杂度理论家认为不是），也未见 P 算法。它是「NP 中间地带」的头号候选。

任何有限群生成集下，凯莱图的直径至多 (log n)^C（C 为绝对常数）。

现状Babai–Szemerédi 1984 起的多项式对数上界（(log n)⁵ 级）是最好一般结果；把指数压到常数需要「乘积混洗」之外的统一思想。它与展开图理论、随机游走混合率交织。

拟阵的任意 n 个基可排成 n 列，使每行是一个基且任意前 k 列拼成前 k 个基的不交并（可交换性）。

现状对可表示拟阵的 n≤3 情形、强基可序拟阵与直积闭包已证；一般拟阵连 n=4 都悬置。它是拟阵论向「代数稳定型」延伸的试金石。

给定一个双变量多项式，判定它是否是某个（拟阵/图）的塔特多项式——复杂度与完全刻画是什么？

现状一般 #P-难；「哪些多项式是塔特多项式」的代数刻画（Huh–Katz 的洛吉-凹性只给出必要条件）远未完成。「塔特多项式的像」这个集合的几何形状是代数组合的新前沿。

两个凯莱图同构何时能由生成元的群自同构解释（CI 性质）？对哪些群与生成集成立？

现状原始 Ádám 猜想有反例；修正版对循环群（Alspach 定理大量情形）与交换群部分成立。它与「凯莱图的系统枚举」「图同构的限制版」直接相关。

3-色判定能否在 O(cⁿ 且 c<1.328）内完成？目前最好约 1.3289（Beigel–Eppstein 后的改进）。

现状自 2001 年 Beigel–Eppstein 后仅微幅改进；强指数时间假设（SETH）预测存在下界但不可证。它是「指数算法的极限在哪里」的样本问题。

度量 TSP 是否有近似比 4/3 的多项式算法（下界即已知的 4/3 硬度）？

现状Karlin–Klein–Oveis Gharan 2020 打破 45 年的 3/2（Christofides），得到 3/2−ε（ε≈10⁻³⁶）；把 ε 做成实质数字直至 4/3，是组合优化最热的开放赛道。

塔特定理（4-连通平面三角剖分哈密顿）能否去掉「三角剖分」条件？

现状1966 年以来无一般证明也无反例；Barnette 猜想（22 号）是其二部版。「4-连通平面 + 无三角」的中间地带同样开。

任何有限的「并对称」集族（两元素之并仍在族中）中，至少有一半集合含有某个固定元素。

现状1979 年提出，Polymath1 攻而不克。已证下界从 3n/(n+4) 爬到约 0.613（Knill 型递归+熵方法），距 1/2 的目标还差 0.1+；与信息论、交换代数（Stanley 型）都有联系。

比值 R(k,k)/4^k（或其多项式修正）随 k→∞ 是否有极限？

现状「随机图 Ramsey」的浓度结果（如 R(k,k) 集中在窄窗）都只是条件型；极限存在性需要把 03 号问题的指数世界压缩成单一常数，目前没有任何方法触及。

「同谱不同构」的图对是否只占渐近零比例？（GDS 问题：谱确定图）

现状大量特殊图类（树、部分正则图）有同谱伙伴；随机图的谱方法（如特征值间隙）支持「几乎唯一」，但严格证明被「重根结构」卡住。它与量子图论（Google 型量子步行的可区分性）直接相关。

能否把 Appel–Haken / Robertson–Sanders–Seymour–Thomas 的可约性检查压缩到人类可核验的规模（如数十个构形、几页代数）？

现状633 个构形（RST 版）仍是计算机助力的。若 Hadwiger 猜想 k=5 或 Barnette 猜想获证，将自动给出短证明——「可读四色」因此是结构图论的路标而非纯哲学诉求。

χ-染色需要 ≥ k 色的图包含 K_k 的拓扑子式（细分拷贝）——哈德维格猜想的细分版。

现状对 k≤5 已证；k