关于图的色数χ(G)为何是NP难而非NP完全的疑问及推理验证

最近我琢磨了个关于图着色问题的想法，想跟大家捋一捋，也请各位帮忙看看有没有疏漏：

注：以下推理的基础信息可能需要进一步核实

我们知道，判断一个有N个顶点的图是否能用K种颜色着色是NP完全问题。现在聚焦那些可以在多项式时间内完成判定的场景，同时图的色数χ(G)的上下界（暂不考虑各类优化）是1到K之间的整数——这个结论可以通过布鲁克斯定理推导出来，而且色数肯定是整数，不可能出现半值的情况。

那我就有个疑问了：我们不是可以用$\lceil\log_{2}\left(K\right)\rceil$次猜测来定位1到K之间的某个整数吗？也就是说，如果判定图是否可K着色的时间复杂度是$O\left(K^{{c}\right)$（多项式时间），那计算χ(G)的时间复杂度不就是$\lceil\log_{2}\left(K\right)\rceil*O\left(K}{c}\right)$？而这个结果可以简化为$O\left(K^{c}\right)$，那这是不是意味着求χ(G)也是NP完全问题？

编辑补充：其实我们是不是也可以在多项式时间内验证χ(G)的取值？比如假设A是色数，我们只需要完成两个验证：一是A-1种颜色无法给图着色，二是A种颜色可以给图着色——而这两个步骤本质上就是前面提到的判定问题，属于NP完全级别的操作。那这样的话，如果P=NP，这两个验证就能在多项式时间内完成；如果P≠NP，那求χ(G)就是NP难的？

虽然这不是说能直接在多项式时间内求出χ(G)的精确值，但结合P vs NP的两种情况来看：

• 如果P=NP，那求χ(G)的问题既是NP完全的，同时也属于P类（因为NP完全问题在P=NP时都能在多项式时间内解决）；
• 如果P≠NP，那求χ(G)是NP难的，同时它属于NP类吗？这看起来像是个“双层”的NP完全问题了？

我知道自己可能有考虑不周的地方，就是突然冒出这个想法，想写出来跟大家探讨探讨。

再编辑：刚才那段关于P≠NP时的表述可能有点绕，抱歉。

备注：内容来源于stack exchange，提问作者Lexinathan