证明任意图G的色数小于或等于图的顶点数与团数之和除以二

Question

让我们将图 G 的色数表示为 k，将图 G 的团数（即图 G 中最大的完整子图的大小）表示为 q，将 n 表示为 G 的顶点数，我在显示 k 时遇到了问题<=(n+q)/2.

所以我对任何图 G 的了解是，任何图的色数至少等于团数

团数：图中最大完整子图的大小。

色数：最小颜色数。顶点可以着色，且相邻顶点不共享颜色。

Answer 1

正在进行中的工作；尽早发布，以防对某人有帮助；仍在努力解决这个问题。

目标：证明对于所有图 G, k<=(n+q)/2, terms as defined by op.

通过详尽的搜索很容易证明这适用于所有非常小的图。

假设它并不适用于所有图，并令 n 为至少一个图违反该假设的最小尺寸。在所有大小为 n 的图中，令 G 为边数最少的图。

设 q 为 G 中最大团的大小，并令 C 为 G s.t 中的团。 |C| = q.

令 K(G) = k 为 G 的色数。

然后，根据假设，我们有 k > (n+q) / 2

我们知道 G 不是一个大小为 n 的团，因为如果 n = q，则该图是一个团，并且可以清楚地用 (n+q)/2 = (n+n)/2 = n 颜色进行着色，因此有必须至少有一个不在 C 中的顶点。选择任何这样的顶点并将其称为 v。

情况 1：n+q 是偶数

• 设 G' = G \ {v}
• k = K(G) > (n+q)/2 => k >= (n+q)/2 + 1
• k' = K(G') <= (n+q-1)/2 => k' <= (n+q)/2 - 1
• => k - k' >= [(n+q)/2 + 1] - [(n+q)/2 - 1] = 2
• 矛盾。添加/删除一个顶点以及与其相连的任意边最多只能影响色数 1。

情况 2：n+q 是奇数，G 有一些顶点 w，它是每个大小为 q 的团的一部分

• 设 G' = G \ {w}
• k = K(G) > (n+q)/2 => k >= (n+q+1)/2
• k' = K(G') <= [(n-1) + (q-1)] / 2 => k' <= (n+q-3)/2
• => k - k' >= (n+q+1)/2 - (n+q-3)/2 = 2
• 矛盾；推理如上。

---

那么关于 G 一定是真的吗？

• G 中必须至少有两个大小为 q 的派系
• n+q 是奇数
• 在 G 中大小为 q 的所有派系中，至少有一对不共享顶点。

从现在开始，我将在黑暗中尝试一下如何得出证明。

考虑：G如上所述（2+个大小为q的派系，n+q个奇数，一对大小为q的派系不共享顶点）； w G 中的任意顶点

• 设 G' = G \ {w}
• k = K(G) > (n+q)/2 => k >= (n+q+1)/2
• k' = K(G') <= [(n-1) + (q)] / 2 = (n+q-1)/2
• => k - k' >= (n+q+1)/2 - (n+q-1)/2 = 1。

这并不矛盾，但我们知道删除任何顶点都会使 G 的色数减少 1。

但这意味着G 中的所有顶点的度数 >= k-1。否则，我们可以采用任何实现 G' = G{w} 色数的着色，添加顶点 w，添加适当的边，并为 w 提供它不相邻的 q - deg(w) 颜色之一。

所以我们有 k >= (n+q+1)/2，并且 n >= 2q，因为 G 中有两个大小为 q 的不相交派系。=> k >= (3q+1)/2。