着色：顶点、边、列表与完美图
proper vertex coloring（正常顶点着色） 要求每条边的两个端点取不同颜色；能办到的最少颜色数就是图的色数 χ(G)。色数难算（一般图上是 NP-hard），但有一个人人会写的近似办法——greedy coloring（贪心着色）：把顶点排成一个序，逐个给它分配「邻居尚未用过的最小编号颜色」。本页单步演示这套贪心，并让你切换顶点序，直接看到同一张图、不同的序，贪心实际用掉的颜色数会不同。
贪心着色给出一个朴素上界：χ(G) ≤ Δ(G) + 1，其中 Δ 是最大度。理由是，轮到任一顶点时，它至多有 Δ 个已着色的邻居，占掉至多 Δ 种颜色，因此 {1，…，Δ+1} 里必有一种可用。下界则来自团 (clique)：一个
k 个顶点两两相邻的团里，这 k 个点必须两两异色，故 χ(G) ≥ ω(G)，ω 是最大团规模。
单步看上去毫无悬念，但顶点序的影响极大。在皇冠图（crown graph，即完全二部图 K_{n,n} 去掉一组完美匹配）上，真正的色数是 2；然而存在一种「交替挑两侧」的坏序，会逼着贪心一路开到 n 种颜色——贪心着色的最坏表现可以离 χ 任意远。读数里的
ω 是最大团下界，贪心用色数永远夹在 ω 与 Δ+1 之间。
Vizing 定理 · edge coloring（边着色） 要求相邻（共端点）的边异色，所需最少颜色数记 χ'(G)。显然 χ'(G) ≥ Δ（某顶点的 Δ 条边两两相邻）。Vizing 证明了对任意简单图（无重边），反向也几乎成立：χ'(G) ∈ {Δ, Δ+1}。边着色的取值被锁死在仅有的两档里——判定到底是 Δ 还是 Δ+1 仍是难题（König 定理给出：二部图必为 Δ）。
list coloring / choosability（列表着色 / 可选性）： 把单一调色板换成「每个顶点 v 各有自己的可选色单 L(v)」，要求给每点从它自己的单子里取色、仍满足相邻异色。若任意为各点配上大小
的色单都能成功着色，就说图是 k-choosable，最小这样的 k 记 list chromatic number ch(G)。恒有 ch(G) ≥ χ(G)，且差距可以很大：完全二部图 K_{m,m} 的 χ 始终是 2，ch 却随 m 增大而无界。
perfect graph（完美图）： 一张图称为完美图，当且仅当它的每一个 induced subgraph（导出子图）H 都满足 χ(H) = ω(H)——色数恰好等于最大团，下界处处取等，没有任何「隐藏的着色障碍」。二部图、区间图、弦图都是完美图。strong perfect graph theorem（强完美图定理，Chudnovsky–Robertson–Seymour–Thomas）
给出完美图的完整刻画：一张图完美，当且仅当它既不含长度 ≥ 5 的奇洞 (odd hole)、也不含其补 (odd antihole) 作为导出子图。
本页的贪心、χ、χ'、list coloring、完美图只是着色理论的一隅。最著名的结果——四色定理 (Four Color Theorem)：任何平面图 (planar graph) 都满足 χ ≤ 4——是其中的一座高峰，但着色理论远不止于平面情形。延伸阅读见 平面图 与 图的基本语言 里的二部判定（χ ≤ 2 的充要刻画）。