On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
复制标题
关于超常数颜色数的4可色图着色的条件硬度
DOI：
10.1007/978-3-642-15369-3_11
复制
发表时间：
2010
影响因子：
18.9
通讯作者：
Igor Shinkar
中科院分区：
文献类型：
--
作者：
Irit Dinur;Igor Shinkar
当3 ≤ q < Q时，我们考虑对给定图G判定χ（G）≤ q或&chi（G）≥ Q的近似着色（q，Q）问题.这个问题的难度在[7]中显示，q = 3，4和任意大的常数Q在唯一博弈猜想[10]的变体下。
我们将这个结果扩展到依赖于给定图的大小的Q值。扩展依赖于我们考虑的结构的参数。按照[7]的方法，我们发现，对参数的仔细计算给出了用lgc（lg（n））色染色4-可着色图的困难性，其中c > 0。通过改进约简的分析，我们证明了在相关的图的条件下，对某些常数c > 0，用lgc（n）色着色一个4-可着色图是困难的。
该论文的主要技术贡献是多数是最稳定定理的一个变体，即在所有每个坐标具有o（1）影响的平衡函数中，多数函数具有最大的噪声稳定性。我们适应我们的应用程序的定理，以获得更好的减少所需的参数之间的依赖关系。
For 3 ≤ q < Q we consider the ApproxColoring(q,Q) problem of deciding whether χ(G) ≤ q or &chi(G) ≥ Q for a given graph G. Hardness of this problem was shown in [7] for q = 3,4 and arbitrary large constant Q under variants of the Unique Games Conjecture [10].
We extend this result to values of Q that depend on the size of a given graph. The extension depends on the parameters of the conjectures we consider. Following the approach of [7], we find that a careful calculation of the parameters gives hardness of coloring a 4-colorable graph with lgc(lg(n)) colors for some constant c > 0. By improving the analysis of the reduction we show that under related conjectures it is hard to color a 4-colorable graph with lgc(n) colors for some constant c > 0.
The main technical contribution of the paper is a variant of the Majority is Stablest Theorem, which says that among all balanced functions whose each coordinate has o(1) influence, the Majority function has the largest noise stability. We adapt the theorem for our applications to get a better dependency between the parameters required for the reduction.