使用着色优化或着色决定来解决着色搜索

Question

你怎么能证明 着色搜索 可以通过对解决方案进行多项式调用来解决 着色优化 或者 着色决定? (着色搜索 是为了使图的顶点着色的算法，以使相邻顶点具有不同的颜色。）

我不确定如何解决，但这是我尝试的（我选择使用 着色优化):

着色搜索 可以通过打电话来解决 着色优化 并找到值$ m $，这是所需的颜色量，因此没有两个相邻的顶点具有相同的颜色。一旦找到$ m $， 着色搜索 可以通过为每个顶点旋转$ m $不同的颜色来为图形的顶点着色。

我在正确的道路上吗？

Answer 1

给定图表$ g $，我们想做两件事：

1. 找到最小的$ k $，这样$ g $是$ k $ - 颜色，
2. 给定这样的$ k $，找到$ g $的颜色，带有$ k $颜色。

如果我们有彩色问题的决策版本的甲骨文，我们可以同时完成两者。

对于第一部分，我们可以执行搜索以找到最佳$ K $。即使是这里的天真方法也可以，我们可以顺序询问$ g $是否为$ k $ - 颜色$ k = 1,2， ldots，n $。然后，我们最多可以向Oracle进行$ N $调用。当然，我们可以执行二进制搜索并将其切成$ log n $调用。 （请注意，这也是我们使用决策版本解决优化版本的方式）。

然后，鉴于我们已经确定了$ k $是最佳的，因此我们可以使用Dikiss Oracle找到$ g $的$ k $颜色。唯一的皱纹是甲骨文不采用部分颜色，因此我们需要在图中编码特定顶点的一种特定颜色的方法。

为此，我们实际上在辅助图上使用了甲骨文，我们将其称为$ g^{+} $，即$ g $加上$ k_ {k {k {k {k} $，并带有一些附加的边缘。当然，$ k_ {k} $完全需要$ k $颜色，因此我们可以使用其顶点来指示哪些颜色可用于顶点。让vertices $ {k_ {1}， ldots，k_ {k} } $的$ k_ {k {k {k {k} $对应于颜色$ {c_ {1}， ldots，c_ {k {k} $。然后，我们将指出$ g $中的顶点$ v $ 不能 通过将其与$ k_ {i} $相邻，用颜色$ c_ {i} $颜色。此外，如果我们用颜色$ c_ {j} $上色，我们将使它与之相邻 每一个 $ k_ {i} $带有$ i neq j $（和 不是 附近$ k_ {j} $）。

然后，我们反复做以下操作：

1. 在v（g）$中选择一个“未颜色”顶点$ v 。
2. 对于n（v）$中的每个顶点$ u ，如果$ u $都被着色，则有一个$ k_ {i} $，因此$ uk_ {i} notin e（g）$。将edge $ vk_ {i} $添加到$ e $。
3. 对于剩余的顶点$ k_ {j} $，因此$ vk_ {j} $尚未在$ e $中，我们添加全部 其他 $ v $和$ k_ {k} $之间的边缘，并询问Oracle是否新图为$ k $ - 颜色。如果是这样，我们将其保留并继续进入下一个顶点，如果答案为否，我们会撤消步骤3，然后尝试下一个$ k_ {j} $。

请注意，由于$ g $是$ k $ - 颜色，因此有一些$ k_ {j} $该步骤将与之使用。然后，当我们处理每个顶点时，$ g $中的每个顶点是 不是 恰好在$ k_ {k} $中的一个顶点附近，这表明可以使用哪种颜色颜色来获得着色。从步骤2开始，我们看到这与其任何邻居的颜色不可能相同。

在第三步中，我们最多可以$ k $呼叫Oracle，我们为$ G $中的每个顶点做到这一点，因此我们总共最多可以$ $（K+1）n $调用Oracle（包括搜索对于$ k $）。