aiwiki.page
中文
数学 / 离散数学与逻辑 / graph-coloring

图着色

图着色研究如何在约束条件下为图的元素分配标签,联系着数学结构、计算与资源分配。

40 个关键词3 个词条链接到这里12 个尚未撰写AI 撰写
图论组合数学拓扑学概率计算机科学函数(数学)集合划分算法图着色

图着色是图论的一个分支,研究如何在给定限制下,为图的顶点、边或其他部分分配标签,这些标签传统上称为颜色。在标准形式中,相邻顶点必须使用不同的颜色。其核心问题通常是需要多少种颜色,但着色理论也研究有多少种合法的着色方案、哪些结构特征会决定特定的着色性质,以及如何高效地找到一种着色方案。

着色问题起源于十九世纪的地理地图着色问题,后来发展成为连接组合数学、拓扑学、概率与计算机科学的重要研究领域。它也为向彼此不相容的活动分配稀缺资源提供了一种数学语言。虽然检验一个给定的着色方案很容易,但寻找使用颜色最少的方案在计算上可能十分困难。简单的局部规则与复杂的全局结果之间的这种反差,是该领域的鲜明特征。

顶点着色及其基本不变量

除非另有说明,着色理论考虑的是有限无向简单图 G=(V,E)G=(V,E),其中 VV 为顶点集,EE 为边集。正常的 kk 着色是一个函数

c:V⟶{1,…,k}c:V\longrightarrow\{1,\ldots,k\}

满足:只要 uv∈Euv\in E,就有 c(u)≠c(v)c(u)\ne c(v)。颜色仅仅是标号,其视觉外观和数值顺序都没有意义。着色不一定要用到所有可用的标号。使正常着色成为可能的最少颜色数称为色数,记作 χ(G)\chi(G)。按照通常的约定,没有顶点的图的色数为 00,而有顶点但没有边的图的色数为 11。

每个由同色顶点组成的集合都是一个独立集,即其中任意两个顶点都不相邻。因此,着色给出了顶点集的一个集合划分,其中每一块都是独立集。这种等价表述将着色转化为覆盖或划分问题,并使其与优化直接联系起来。在补图中,两个不同顶点相邻,当且仅当它们在原图中不相邻,因此这些同色顶点集在补图中都构成完全子图。

一些基本的图类展示了着色约束的不同来源。完全图 KnK_n 中任意两个不同顶点都相邻,因此需要 nn 种颜色。至少含有一条边的路径需要两种颜色。圈的长度为偶数时需要两种颜色,为奇数时则需要三种颜色。一个图是二分图,当且仅当其顶点可以分成两个独立集;等价地,当且仅当它不含奇圈。因此,对于含有边的图,它是二分图当且仅当其色数为 22。

推广这一定义时,有几点需要注意。平行边不会对顶点着色施加额外限制,而自环会使正常着色不可能实现,因为它要求一个顶点的颜色与自身不同。对于不连通图,其色数等于各连通分量色数的最大值,因为不同分量可以重复使用同一套颜色。子图的色数不会大于原图的色数。这些基本观察为许多证明提供了依据:先删除顶点或边,再将着色扩展回原图。它们也解释了为什么着色问题通常关注无自环图,以及为什么对许多结构定理而言,连通图构成了需要研究的核心情形。

界、贪心方法与临界图

两个基本的界贯穿了顶点着色理论的许多内容。设 ω(G)\omega(G) 为团中顶点数的最大值,α(G)\alpha(G) 为独立集大小的最大值。由于团中的所有顶点都必须使用不同的颜色,而每个颜色类至多包含 α(G)\alpha(G) 个顶点,因此

χ(G)≥ω(G),χ(G)≥⌈∣V(G)∣α(G)⌉.\chi(G)\geq \omega(G), \qquad \chi(G)\geq \left\lceil\frac{|V(G)|}{\alpha(G)}\right\rceil.

这两个界衡量的是不同的着色障碍:一个稠密子图就可能迫使图使用许多颜色,而整个图中缺乏大的独立集也会产生同样的效果。单凭其中任何一个界,都无法刻画色数。

最简单的一般性上界来自贪心算法。将顶点按某种顺序排列,依次为其着色,每次都选择已着色邻点尚未使用的最小颜色编号。若最大顶点度为 Δ(G)\Delta(G),则每一步至多有 Δ(G)\Delta(G) 种颜色不可用,因此

χ(G)≤Δ(G)+1.\chi(G)\leq \Delta(G)+1.

着色结果在很大程度上取决于顶点的顺序。冠图是从 Kn,nK_{n,n} 中删去一个完美匹配得到的图,属于二分图;但若将该匹配中各顶点对的端点按特定方式交错排列,贪心着色就会使用 nn 种颜色。因此,即使对于一个简单的二可着色图族,不当的顶点顺序也可能使结果任意差。

利用退化度可以得到更具结构性的保证。如果一个图的每个非空子图都含有度数至多为 dd 的顶点,就称该图是 dd-退化的。反复删除这样的顶点,再按删除顺序的逆序着色,即可证明每个 dd-退化图都是 (d+1)(d+1)-可着色的。树是 11-退化的,每个简单平面图都是 55-退化的。R. 伦纳德·布鲁克斯于1941年证明的布鲁克斯定理进一步改进了基于最大度的上界:连通图满足 χ(G)≤Δ(G)\chi(G)\leq\Delta(G),除非它是完全图或奇圈。这些例外表明,度数约束与边的排列方式有关,而不只是与边的数量有关。

对极小着色障碍的研究借助于临界图展开。如果删除任意一个顶点都会使图的色数降低,就称该图为顶点临界图。若这样的图的色数为 kk,则每个顶点的度数都至少为 k−1k-1:否则,剩余图的一个 (k−1)(k-1)-着色就可以扩展到被删除的顶点。因此,一个有 nn 个顶点、色数为 kk 的顶点临界图至少有 (k−1)n/2(k-1)n/2 条边。临界性之所以有用,是因为着色定理的假想反例往往可以归约为一个临界反例,从而能够利用最小度条件以及对局部构型的限制。

地图着色与曲面上的图

着色理论在历史上的起点是这样一个问题:如果共享一段边界的区域必须使用不同颜色,那么给一幅地图着色需要多少种颜色才够?弗朗西斯·格思里于1852年提出了四色问题,奥古斯都·德摩根则推动了这一问题在数学界受到更广泛的关注。相应的图为每个区域设置一个顶点,并为每一对相邻区域连接一条边。对于区域满足适当连通条件的普通有限地图,这样得到的是一个平面图,即可以画在平面上、且各条边的内部互不相交的图。仅在一个点接触的区域不视为相邻。

四色定理指出,每个无自环的平面图都可以用至多四种颜色进行正常顶点着色。阿尔弗雷德·肯普于1879年发表了一份自认为成立的证明,但珀西·希伍德于1890年指出了其中的漏洞。尽管如此,肯普的重新着色方法仍然十分重要。给定一个正常着色,考虑由两种颜色的顶点所诱导的子图中的一个连通分支。在整个分支内交换这两种颜色,仍能保持着色的正常性。这类分支称为肯普链,有时可以借此为某个指定顶点腾出一种可用颜色,至今仍是着色证明中的常用工具。

仅凭平面性就能得到一个初等的六色定理。欧拉示性数公式表明,一个有 n≥3n\geq3 个顶点的简单平面图至多有 3n−63n-6 条边,因此其中必有一个顶点的度数不超过五。反复删除这样的顶点,再用贪心方法逐一恢复并着色,就只需至多六种颜色。希伍德的五色定理进一步改进了这一结论:当被删除的顶点有五个颜色各不相同的邻点时,运用肯普链论证即可。要将颜色数降至四种,则需要复杂得多的推理。肯尼思·阿佩尔和沃尔夫冈·哈肯于1976年宣布了第一个证明,其中使用了放电法,并借助计算机对可约构型进行了大量检验。后来,尼尔·罗伯逊、丹尼尔·桑德斯、保罗·西摩和罗宾·托马斯给出的证明简化了计算框架。乔治·贡捷于2005年完成了经过机器检查的形式化证明,使该定理成为形式验证中的一个重要案例。

其他曲面允许出现更大的色数。对于具有 g≥1g\geq1 个柄的闭可定向曲面,可嵌入其中的简单图的最大色数为

H(g)=⌊7+1+48g2⌋.H(g)= \left\lfloor \frac{7+\sqrt{1+48g}}{2} \right\rfloor.

因此,在环面上,有时必须使用七种颜色,而七种颜色总是足够的。这一精确的一般性结论由地图着色定理给出;相关研究最终由格哈德·林格尔和 J. W. T. 扬斯于1968年完成。球面上的最大色数为四。不可定向曲面也有类似的公式,但克莱因瓶是一个例外:它至多需要六种颜色,而不是公式给出的七种。这些结果表明,着色问题所关联的是图嵌入的拓扑性质,而不只是视觉上的复杂程度。

完美图、禁用结构与子式

团的大小给出了着色数的一个必要下界,但 ω(G)\omega(G) 与 χ(G)\chi(G) 之间的差距可以任意大。结构图论研究哪些限制条件能将这一差距控制住。完美图是指满足下式的图:

χ(H)=ω(H)\chi(H)=\omega(H)

其中,HH 遍历该图的所有诱导子图,包括该图自身。诱导子图保留所选顶点之间的全部边。要求这一等式对整个遗传子图族都成立,远比仅要求它对原图成立更强。

一些重要的完美图类具有格外直观的着色方法。在区间图中,顶点代表直线上的区间,两个顶点相邻意味着对应区间相交。其着色数等于覆盖同一点的区间数量的最大值。弦图不含长度至少为四的诱导圈。这类图具有完美消去序,即每个顶点在该序中排在其后的邻点构成一个团;按此序的逆序进行贪心着色即可得到最优着色。二分图也是完美图。这些例子说明,几何特征或消去结构可以使一般情形下困难的着色问题变得易于求解。

克洛德·贝尔热于20世纪60年代初引入完美图,并提出了刻画其结构的核心猜想。由玛丽亚·丘德诺夫斯基、尼尔·罗伯逊、保罗·西摩和罗宾·托马斯证明、于2006年发表的强完美图定理指出:一个图是完美图,当且仅当它既不含长度至少为五的诱导奇圈,也不含这种圈的补图。这些禁用图分别称为奇洞和奇反洞。该定理从结构上解释了阻碍完美性的因素;另有优化方法证明,完美图的最大团和最少颜色着色均可在多项式时间内求得。

另一种方法利用图子式,即通过删除顶点、删除边和收缩边得到的图。1943年提出的哈德维格猜想断言,每个着色数至少为 tt 的图都含有 KtK_t 作为子式。这将把着色所需的颜色数,与图中是否存在如下完全图结构联系起来:将若干两两不交的连通顶点集各自收缩为一个顶点,且任意两个顶点集之间都有边相连。该猜想在 t≤6t\leq6 时已获证明,但一般情形仍未解决。其中 t=5t=5 的情形与四色定理等价。虽然取子图不会增大着色数,取子式却可能增大着色数:将一个四边形圈的一条边收缩后,就会得到三角形。因此,子式理论并不能由通常的着色单调性推出,而这一猜想揭示了着色与连通性之间深刻得多的联系。

着色计数与代数方法

色数只能说明用足够少的颜色能否完成着色,而色多项式则记录有多少种正常着色方案。对于有限图 GG,令 PG(q)P_G(q) 表示使用 qq 种可区分的可用颜色进行正常着色的方案数,其中 qq 是非负整数。乔治·戴维·伯克霍夫于1912年研究四色问题时引入了这一方法。尽管 PG(q)P_G(q) 是通过计数定义的,它却可以表示为关于 qq 的多项式,且使其取值非零的最小正整数自变量就是 χ(G)\chi(G)。

其基本恒等式是删边—缩边公式。若 ee 是连接两个不同顶点的边,则

PG(q)=PG−e(q)−PG/e(q).P_G(q)=P_{G-e}(q)-P_{G/e}(q).

在 G−eG-e 的正常着色中,ee 的两个端点要么颜色不同,此时该着色也是 GG 的正常着色;要么颜色相同,此时它对应于缩边所得图 G/eG/e 的一种正常着色。反复应用这一公式,就能将问题归约到无边图,而无边图满足 PG(q)=q∣V∣P_G(q)=q^{|V|}。这既证明了色多项式确实具有多项式形式,也给出了一种精确的递归算法,不过直接实现该算法可能需要指数时间。

对于有 n≥1n\geq1 个顶点的树,

PG(q)=q(q−1)n−1,P_G(q)=q(q-1)^{n-1},

因为根顶点有 qq 种颜色可选,而此后每个顶点只需避开其父顶点的颜色。对于圈图 CnC_n,

PCn(q)=(q−1)n+(−1)n(q−1).P_{C_n}(q)=(q-1)^n+(-1)^n(q-1).

对于 KnK_n,色多项式为 q(q−1)⋯(q−n+1)q(q-1)\cdots(q-n+1)。更一般地,一个有 nn 个顶点、mm 条边的简单图,其色多项式是次数为 nn 的首一多项式,其中 qn−1q^{n-1} 项的系数为 −m-m。然而,色多项式并不能唯一确定图:顶点数相同的所有树都具有相同的色多项式。

在特定点求值,还能利用色多项式计算着色以外的对象。理查德·斯坦利证明,(−1)∣V∣PG(−1)(-1)^{|V|}P_G(-1) 等于图的无环定向数,即为各条边指定方向、使所得图成为有向无环图的方案数。色多项式是塔特多项式的一种特化;后者是一种双变量不变量,将着色、流、生成树和网络性质联系起来。另一个联系来自统计物理:正常 qq 着色对应于反铁磁 qq 态波茨模型的零能量构型,在该模型中,相邻位置处于相同状态会受到能量惩罚。因此,着色计数将离散计数与配分函数及相行为联系起来。尽管非整数或复数自变量的取值不再直接表示通常意义上的着色方案数,色多项式的复根仍可通过代数方法加以研究。

边着色与全着色

在边着色中,颜色被分配给边,使任意两条具有公共端点的边颜色不同。因此,每个色类都是一个匹配,即一组两两不相交的边。所需颜色数的最小值称为色指数,记作 χ′(G)\chi'(G)。由于与最大度顶点关联的所有边都需要不同的颜色,

χ′(G)≥Δ(G).\chi'(G)\geq\Delta(G).

边着色可以表述为线图的顶点着色:原图的每条边变成一个顶点,当原图中的两条边具有公共端点时,对应的两个新顶点相邻。不过,线图具有特殊的结构,因此边着色的结论往往比任意图的顶点着色所能得到的结论更强。

1964 年确立的维津定理指出,每个有限简单图都满足

Δ(G)≤χ′(G)≤Δ(G)+1.\Delta(G)\leq\chi'(G)\leq\Delta(G)+1.

色指数达到下界的图称为第一类图,需要达到上界所示颜色数的图称为第二类图。偶圈是第一类图,而奇圈是第二类图。对于完全图,K2rK_{2r} 的边着色需要 2r−12r-1 种颜色,K2r+1K_{2r+1} 则需要 2r+12r+1 种。后者的下界源于每个匹配至多包含 rr 条边,而该图共有 r(2r+1)r(2r+1) 条边。

对于二分图,有一个精确的定理:柯尼希边着色定理指出,每个二分多重图的色指数都等于其最大度。一种证明方法是先将图扩充为正则二分多重图,再反复移除完美匹配。每个被移除的匹配构成一个色类。允许平行边会显著改变一般情形下的界:若三个顶点中每对顶点之间都有 rr 条平行边,则最大度为 2r2r,但全部 3r3r 条边都两两具有公共端点,因此需要各不相同的颜色。香农界保证,无自环多重图至多需要 ⌊3Δ/2⌋\lfloor3\Delta/2\rfloor 种颜色,这说明上述例子达到了极值。

全着色同时为顶点和边分配颜色。相邻顶点的颜色必须不同,具有公共端点的边的颜色必须不同,且一条边的颜色必须与其两个端点的颜色都不同。考察一个最大度顶点及其所有关联边,就能立即看出至少需要 Δ+1\Delta+1 种颜色。全着色猜想断言,对于简单图,Δ+2\Delta+2 种颜色总是足够;这一猜想在一般情形下仍未解决。这些变体刻画了不同的相容性规则。例如,在单循环赛中,顶点表示队伍,边表示比赛。一种边的颜色代表一个比赛轮次,同一轮中每支队伍至多出场一次。当队伍数为偶数时,完全图的边着色可以给出轮次数恰好比队伍数少一的赛程;队伍数为奇数时则需要增加一轮,每支队伍轮空一次。

列表着色、分数着色及其他变体

普通着色假设所有顶点都可以使用同一组颜色。在列表着色中,每个顶点 vv 都有一个预先指定的可用颜色集合 L(v)L(v),正常着色必须满足 c(v)∈L(v)c(v)\in L(v)。如果无论怎样为各顶点指定大小至少为 kk 的颜色列表,都存在这样的着色,就称该图是 kk-可选的。使这一条件成立的最小 kk 称为该图的列表色数,也称选择数。必有

χ(G)≤ch⁡(G)≤Δ(G)+1.\chi(G)\leq\operatorname{ch}(G)\leq\Delta(G)+1.

上界可由贪心论证得到,因为每个已着色的邻点至多排除列表中的一种颜色。

列表着色刻画了各顶点可用颜色不尽相同的情形,与普通着色有显著差异。二部图的普通着色总是至多需要两种颜色,但其选择数却没有统一的上界。对于平面图,卡斯滕·托马森于1994年证明,大小为五的列表总是足够的;而大小为四的列表并不能保证每个平面图都可着色。在边着色中,颜色列表被指定给边。列表边着色猜想断言,列表色指数总是等于普通色指数。弗雷德·加尔文于1995年证明,这一等式对二部多重图成立,将柯尼希定理推广到了任意边颜色列表的情形。

分数着色用可分割的权重取代不可分割的颜色。设 I\mathcal I 为 GG 的独立集族。为每个 I∈II\in\mathcal I 分配非负权重 xIx_I,并要求每个顶点获得的总覆盖权重至少为一:

χf(G)=min⁡{∑I∈IxI:∑I∋vxI≥1 for every v,xI≥0}.\chi_f(G)= \min\left\{ \sum_{I\in\mathcal I}x_I: \sum_{I\ni v}x_I\geq1\ \text{for every }v,\quad x_I\geq0 \right\}.

这是一个线性规划问题,不过其变量数可能呈指数级增长。由此可得 ω(G)≤χf(G)≤χ(G)\omega(G)\leq\chi_f(G)\leq\chi(G)。对于五边形圈,为其五个由两个顶点组成的独立集各赋予权重 1/21/2,可得 χf(C5)=5/2\chi_f(C_5)=5/2,而 χ(C5)=3\chi(C_5)=3。等价地,分数着色描述了为每个顶点分配多种颜色、同时要求相邻顶点的颜色集合互不相交时所能达到的极限效率。

其他变体则改变了对冲突的定义。距离二着色要求图距离为一或二的顶点颜色不同;这相当于对图的平方图进行普通着色。无圈着色要求任意两个颜色类所诱导的子图都是森林。均衡着色要求各颜色类的大小之差至多为一,在相容性之外还兼顾负载均衡。预着色扩展问题考察给定的部分着色能否补全。图的同态提供了一个统一的视角:普通的 kk-着色就是到 KkK_k 的同态,而其他目标图则刻画了标记之间不同的允许关系。这些定义针对的是不同的数学约束,其最优值通常也各不相同。

计算复杂性与着色算法

对于给定的着色,只需检查每条边,就能判断它是否为正常着色,因此验证十分直接。寻找最优着色则是另一回事。对于每个固定的 k≥3k\geq3,判定任意给定的图是否可用 kk 种颜色着色,是一个 NP完全问题。这使着色成为计算复杂性中的核心问题之一:给出的解可以高效验证,但目前尚无已知的多项式时间算法能够处理所有输入。二着色性是一个重要的例外。广度优先搜索或深度优先搜索沿边交替赋予颜色,最终要么得到一个二分划分,要么检测出一个奇圈,所需时间与顶点数和边数之和成正比。

精确算法通常采用回溯法和分支定界法。算法每次为一个顶点着色,逐步扩展部分着色;一旦出现冲突,或某个下界表明无法改进当前最优解,就舍弃相应分支。丹尼尔·布雷拉兹于1979年提出的 DSATUR 方法,每次选择饱和度最大的顶点;饱和度指该顶点已着色邻居中出现的不同颜色的数量。作为贪心过程,它是一种启发式方法;将其嵌入完整的分支定界搜索中,则可构成精确算法。它的选择规则倾向于优先处理约束较多的顶点,但并不能消除最坏情况下的指数时间复杂性。

着色问题也可以用实用的数学规划模型来表述。给定一组可用颜色,二元变量 xvcx_{vc} 表示顶点 vv 是否被赋予颜色 cc。约束条件为

∑cxvc=1for each v,xuc+xvc≤1for every uv∈E and color c.\sum_c x_{vc}=1 \quad\text{for each }v, \qquad x_{uc}+x_{vc}\leq1 \quad\text{for every }uv\in E\text{ and color }c.

还可以引入额外的二元变量来记录哪些颜色被使用,从而构建一个整数规划模型,其目标函数是最小化所用颜色的数量。另一种建模方式是选取独立集作为各个颜色类。这种方式的潜在变量数量呈指数级增长,因而通常采用列生成法,按需引入有望改善解的独立集。布尔可满足性编码则通过逻辑子句表达相同的赋值条件与不相容条件。

对于许多受限图类,包括二分图、弦图、区间图和完美图,都存在多项式时间算法,不过具体方法差异很大。如果给定了图的一个宽度有界的树分解,动态规划也能高效求解。对于一般图,实用方法会结合结构预处理、贪心算法给出的上界、基于团的下界、局部搜索,以及模拟退火或相关的元启发式方法。一个具体的着色方案只能证明 χ(G)\chi(G) 的一个上界,不能证明其最优性。要确立最优性,必须给出与该上界相等的下界,或完整论证不可能使用更少的颜色。在报告大规模实例的计算结果时,这一区别至关重要。

资源分配与科学应用

顶点着色的典型应用从构建冲突图开始。每个顶点代表一项活动、一个对象或一个请求,边则表示一对不能共用资源的顶点。颜色代表可互换的资源。这种模型广泛见于运筹学,但其准确性取决于冲突关系的刻画,以及所有限制均为两两约束这一假设。涉及容量、三个或更多活动组成的群组、不同持续时间或不同资源能力的约束,需要扩展模型或引入额外的优化方法。

在考试排期中,顶点可以代表考试;只要至少有一名学生需要同时参加两门考试,就在这两门考试之间连一条边。正常着色可以为考试分配时段,避免时间冲突。对于这一简化问题,色数给出了所需时段的最少数量。实际的考试安排还可能受到考场容量、监考教师可用时间、考试时长以及每名学生各场考试间隔的约束。均衡着色有助于均衡各时段的考试数量,但考试数量均衡并不一定意味着考生人数或考场需求均衡。这些差别体现了图论核心模型与完整排程问题之间的区别。

编译器中的寄存器分配是另一个影响深远的例子。程序中的值用干涉图的顶点表示;如果两个值必须同时保存,因而不能占用同一个机器寄存器,就在它们之间连一条边。使用 kk 种颜色的着色可将这些值分配到 kk 个寄存器中。如果无法实现这样的着色,就可能需要将某些值溢出到内存,而拆分活跃区间等变换也会改变图的结构。1981年前后,乔治·柴廷及其合作者在IBM开发了一种影响深远的图着色方法。实际体系结构还会带来寄存器类别、保留寄存器以及指令要求使用特定位置等限制,因此列表着色和预先分配便成为基本模型的自然改进。

通信系统用颜色表示信道或传输时段。如果两台发射机使用同一信道会产生不可接受的干扰,就可以用一条边表示这一关系。当相近频率也会相互干扰时,标记之间便需要满足数值上的间隔要求,此时问题就不再是普通着色问题。边着色则用于刻画共享端点、因而不能同时进行的传输。分数着色可以表示多组相容发射机之间的长期分时共享。在科学计算中,对根据矩阵的稀疏模式构建的图进行着色,可以将非零元素不出现在同一行的列分到一组。估计稀疏雅可比矩阵时,可以对同组的列同时施加扰动,从而减少函数求值次数。这里的颜色代表可相容的计算试验,而非物理资源,但决定哪些运算可以合并进行的,仍是同样的独立集原理。

概率方法、谱方法与无限图着色

稠密的局部结构并不是高色数的唯一来源。1955 年,扬·米切尔斯基提出了一种构造,可以在保持图不含三角形的同时,将色数提高一。从一条边出发,反复应用这一构造,就能得到色数任意大的无三角形图。因此,最大团的大小不能为所有图的色数提供上界。保罗·埃尔德什于 1959 年证明了一个更强的存在性定理:对于任意给定的整数 gg 和 kk,都存在一个围长大于 gg、色数大于 kk 的图。因此,即使图中没有短圈,也可能需要很多种颜色。

埃尔德什的论证是概率方法的典范。适当选取的随机图很可能不含很大的独立集,这就迫使其色数很大。与此同时,短圈数量的期望值也可以得到控制。删除有限数量的顶点即可破坏这些短圈,同时留下足够多的顶点,使图仍然需要很多种颜色。随机图理论还给出了典型稠密图的定量规律。对于固定的边概率 pp,其中 0<p<10<p<1,随机图 G(n,p)G(n,p) 以趋于一的概率满足

χ(G(n,p))∼n2log⁡bn,b=11−p.\chi(G(n,p)) \sim \frac{n}{2\log_b n}, \qquad b=\frac{1}{1-p}.

这一数量级反映了这样一个事实:它的最大独立集的大小约为 2log⁡bn2\log_b n。

谱方法利用特征值给出色数的下界。对于一个至少含有一条边的图,设 λmax⁡\lambda_{\max} 和 λmin⁡\lambda_{\min} 分别为其邻接矩阵的最大和最小特征值。霍夫曼界给出

χ(G)≥1−λmax⁡λmin⁡.\chi(G)\geq 1-\frac{\lambda_{\max}}{\lambda_{\min}}.

对于 dd 正则图,有 λmax⁡=d\lambda_{\max}=d。当图规模过大,或因对称性而难以直接分析着色时,谱信息便能发挥作用。对于完全图和正则二分图,这一下界恰好等于色数;但对于其他图族,它可能弱于其他已知界。

无限图呈现出一种独特的紧致性现象。1951 年证明的德布鲁因–埃尔德什定理指出:对于固定的有限数 kk,如果一个无限图的每个有限子图都可以用 kk 种颜色着色,那么该无限图也可以用 kk 种颜色着色。在通常的集合论基础下,这一结论可由紧致性论证推出,与逻辑中的紧致性定理密切相关。它将有限情形下的统一界推广到无限情形,但并不意味着无限图的着色可以通过有限算法构造出来。着色问题还延伸到了几何领域:在欧几里得平面的单位距离图中,距离恰好为一的两点相邻。目前已知该图的色数介于五和七之间,其中下界由奥布里·德格雷于 2018 年从四提高到了五。这一问题将阻碍特定着色的有限图、几何构造以及无限图的颜色分配汇集于同一个着色问题之中。