顶点序：贪心的全部变数

贪心着色的过程本身没有任何可调参数：沿一个顶点序逐点扫过，每个点取邻居尚未占用的最小编号颜色。图是题目给的，于是全部变数都落在序上。这个变数不小：皇冠图（crown graph，完全二部图 $K_{m,m}$ 去掉一组完美匹配）在 $m = 4$ 时真实色数是 2，按下标序贪心恰好 2 色，而左右交替的坏序把同一个贪心逼到 4 色；$m$ 越大，交替坏序的用色越多，离 $\chi = 2$ 任意远。坏序如何一步步得逞，着色：顶点、边、列表与完美图 里有单步演示；本页不重复单步，改做批量实验——随机序的用色分布长什么样，两种静态启发式序又能把用色压到哪。

无论什么序，贪心用色不超过 $\Delta + 1$（$\Delta$ 为最大度）：轮到任何一点时，已着色的邻居至多 $\Delta$ 个，占不满 $\Delta + 1$ 种颜色。序的好坏，体现在实际用色落在这条上界与下界 $\omega$（最大团规模）之间的哪个位置。

1 · 随机序下的用色分布

坏序既然存在，随机排一个序有多容易踩中？皇冠图 $m = 6$ 上取 100 个随机序（seed 从 1 到 100，逐个可复现），85 次拿到 2 色，13 次 3 色，4 色只出现 2 次；交替坏序能把用色一路推到 $m$，抽样里最坏不过 4 色。Grötzsch 图上同样跑 100 个随机序，97 次 4 色、3 次 5 色。Grötzsch 图无三角形（$\omega = 2$）而 $\chi = 4$，是团下界失效的标准反例，但「$\chi$ 离 $\omega$ 远」并没有让随机序更容易翻车。两组分布说的是同一件事：贪心的最坏情况可以任意差，平均表现却不坏，坏序在随机分布里是小概率事件。挑序的启发式要争的，与其说是避开罕见的灾难，不如说是把「多数时候命中」变成「每次都命中」。

2 · 度降序与退化序

两种经典的静态启发式都赶在扫描开始前给「难点」排位。

度降序（Welsh–Powell 序）把顶点按度从大到小排。直觉是度大的点约束多、可选颜色最紧，趁调色板还空着先安置它们；度小的点无论轮到多晚都好办。

smallest-last 序反着构造：反复从剩余图里摘掉当前度最小的点，全部摘完后，把摘除顺序颠倒过来作为着色序。构造过程顺带给出一个图参数：摘除时刻的度的最大值，称为退化度（degeneracy），记 $d$。沿 smallest-last 序着色时，轮到任何一点，它已着色的邻居恰好是摘除时刻还留在剩余图里的那些邻居，至多 $d$ 个，所以贪心用色不超过 $d + 1$。这条界比 $\Delta + 1$ 细：$\Delta$ 量的是最坏一个点的度，$d$ 量的是层层剥离后每层的最小度，排考冲突图上 $\Delta = 3$ 而 $d = 2$。

实测的落点：Petersen 图与 Grötzsch 图的退化度都是 3，排考冲突图是 2。沿 smallest-last 序贪心，排考图用 3 色、Grötzsch 图用 4 色，都等于各自的 $\chi$；两处 $d + 1$ 的保证分别是 3 与 4，界本身就顶在最优值上。皇冠图上它同样体面，$m = 4$ 与 $m = 6$ 都恰用 2 色——理论页里被坏序反复捉弄的那张图，换上这个序就治好了。

3 · 静态序失灵的方式

度降序失灵于无区分力。皇冠图上所有点同度，按度排序排不出任何先后，稳定排序退化为下标序，测试断言的原话是「度降序 (Welsh–Powell) 在皇冠图上救不了场」。下标序在这张图上碰巧是好序（先整列涂完一侧，再涂另一侧），但这份好运来自顶点恰好按左右两侧分组编号，与度无关；换一种顶点编号方式，度降序照样跟着新编号走，好序就没了依据。

smallest-last 的成绩单更好看，但皇冠图上的 2 色是不是退化序的功劳，值得存疑。皇冠图是 $(m-1)$-正则图：第一个被摘的点度数就是 $m - 1$，退化度只能等于 $m - 1$，于是 $d + 1 = m$ 的保证与 $\Delta + 1$ 一样宽，在这张图上什么也没兜住；而全图同度意味着每一步摘谁全由平手规则（同度取最小下标）裁决。手头只有 $m = 4$ 与 $m = 6$ 两个实测点（测试断言「smallest-last 序治好皇冠图」把它们锁定），对一般的 $m$ 没有证明；换一种平手规则，这个 2 色是否保得住，本页没有答案。

更根本的局限是所有静态序共有的：序在着色开始前就定死，而着色过程中不断产生的信息，比如哪个点的邻居已经占掉了最多种颜色，恰恰是挑下一个点最有用的依据。度降序与 smallest-last 都只看图的形状，不看着色的进展。把「先给谁着色」推迟到运行时、按邻居已占的颜色数临场决定，是 DSATUR 的做法，也是下一页的内容。