Why Almost All k-Colorable Graphs Are Easy to Color
Why Almost All k-Colorable Graphs Are Easy to Color
复制标题
为什么几乎所有 k-可着色图都很容易着色
DOI：
10.1007/s00224-009-9231-5
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
Dan Vilenchik
中科院分区：
文献类型：
--
作者：
A. Coja;Michael Krivelevich;Dan Vilenchik
使用 k 种颜色 (k≥3) 对 k 可着色图进行着色是一个众所周知的难题。考虑平均案例分析可以得到更好的结果。在这项工作中，我们考虑具有 n 个顶点和 cn 个边的 k 可着色图上的均匀分布，c 大于某个足够大的常数。我们严格地证明，大多数此类图的所有正确的 k 着色都位于单个“簇”中，并且除了一小部分（尽管是恒定的）顶点之外，所有其他部分都一致。我们还描述了一种多项式时间算法，该算法可以找到这种随机 k 着色图的正确 k 着色，从而断言大多数此类图很容易着色。这应该与非常稀疏的随机图（可着色 whp）的设置形成对比，其中实验结果表明某些边缘密度制度对于许多着色启发法来说是困难的。
Coloring a k-colorable graph using k colors (k≥3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the uniform distribution over k-colorable graphs with n vertices and exactly cn edges, c greater than some sufficiently large constant. We rigorously show that all proper k-colorings of most such graphs lie in a single “cluster”, and agree on all but a small, though constant, portion of the vertices. We also describe a polynomial time algorithm that whp finds a proper k-coloring of such a random k-colorable graph, thus asserting that most such graphs are easy to color. This should be contrasted with the setting of very sparse random graphs (which are k-colorable whp), where experimental results show some regime of edge density to be difficult for many coloring heuristics.