1.3　本章注释

迭代对数算法的基本技术是由Cole和Vishkin[CV86]提出的。最近[RS15]证明了迭代对数算法的log* n严格边界。该技术可以被推广和扩展，例如，可以扩展到环形拓扑结构或具有恒定度的图[GP87，GPS88，KMW05]。将它作为一个子例程使用，可以在迭代对数时间内解决许多问题。例如，人们可以在O（log* n）时间内，以渐近最优的方式对所谓的增长受限图（一种包括许多自然图类的模型，例如单位圆盘图）进行着色[SW08]。实际上，Schneider等人表明，除了着色之外，在增长受限图和其他限制图中许多经典的组合问题都可以在迭代对数时间内解决。对于固定维度d＞2的环形网格的情况，也就是环形拓扑结构向更高维度的泛化，Brandt等人最近证明了4种颜色的着色可以在O（log* n）时间内找到，而3种颜色的着色则需要全局时间[BHK+17]。

在下一章中，我们学习一个关于着色和相关问题的Ω（log* n）下界[Lin92]。Linial的论文还包含了其他一些关于着色的结果，例如，任何对半径为r的d规则树进行着色的算法，其运行时间最多为2r/3，至少需要种颜色。

对于一般图，后面我们将学习以极大独立集为基础的快速着色算法。由于着色表现出功效和效率之间的权衡，因此对于一般图存在许多不同的结果，例如[PS96，KSOS06，BE09，Kuh09，SW10，BE11b，KP11，BE11a，BEPS12，PS13，CPS14，BEK14]。

本章的一些部分也在[Pel00]的第7章中讨论过，例如，定理1.18的证明。