图着色与色数

一个有6个顶点的图的着色。用2种颜色给图着色是不可能的，所以图的色数为3。

一个图着色a的顶点是否分配了一个标签，称为颜色图这样，没有两个相邻的顶点共享相同的颜色。的彩色数字 $\气(G)$的图 $G$是最小的可以进行这种分配的颜色数。最值得注意的是，图表上也存在其他类型的着色边缘色素这可能受到各种限制。

历史上，对图形着色的研究一直与图形着色密切相关平面图形和四色定理，这也是最著名的图着色问题。这个问题为代数图论的发展和图不变量的研究提供了最初的动机，如在这一页讨论。在现代代数图论中，许多未解问题都涉及到色多项式与其图之间的关系。已解决问题的应用已经在诸如计算机科学、信息论和复杂性理论等领域被发现。许多日常问题，比如最小化调度中的冲突，也等价于图形着色。

这个图不是二色的这个图是3色的这个图是4色的

图的色数是图可着色的最小颜色数。这个定义有点微妙，因为它通常不是直接的最小的数量是多少。对于某些类型的图，例如完整( $K_n$)或二部( $K_ {m, n}$)的时候，可能的选择很少，所以我们可以决定 $\气(K_n) = n$因为每个顶点都必须有不同的颜色。色数的最小分量对于快速证明许多基本定理很有用，因为它允许关注极端情况，而不是一般情况(这里是最小化颜色数量的图形着色)。正是因为这个原因，数学家更喜欢这样的定义。

一个图表 $G$被称为 $k$似是而非的如果存在一个图着色上 $G$与 $k$颜色。如果一个图形是 $k$-可着色的，那么它就是 $n$似是而非的任何 $n > k$．一个图的色数至少与其子图的色数一样大。一个图的色数最多比只少一个顶点的子图的色数大1。

考虑到 $n ^ \文本{th}$循环图 $C_n$在哪里 $n > 2$．证明

$\chi(C_n) = \begin{case} 2 & \text{if} n \text{是偶数\\ 3 & \text{if} n \text{是奇数。} \结束{病例}$

---

假设 $n$是偶数。然后, $\气(C_n) \ 1$因为里面有两条相邻的边 $C_n$．但是一个图着色 $C_n$存在于顶点交替被涂成红色和蓝色的地方，所以 $\气(C_n) = 2$．

假设 $n > 2$是奇数。然后, $\气(C_n) \ 1$因为里面有两条相邻的边 $C_n$．此外, $\气(C_n) \ ne 2$由于顶点颜色不能交替，最终被着色的顶点将与红色和蓝色顶点相邻。但是一个图着色 $C_n$存在的地方 $n - 1$顶点交替被涂成红色和蓝色，最后的顶点被涂成黄色，所以 $\气(C_n) = 3$． $_ \广场$

假设一个图 $G$和一个图 $G’$组合起来创建一个图表 $H$通过连接的每个顶点 $G$的每个顶点 $G’$否则所有的顶点和边都保持不变。证明 $\chi(G) + \chi(G') = \chi(H)。$

---

让 $G$有一个图形着色与颜色 $\{1， \， \点，\，\chi(G)\}$而且 $G’$有一个图形着色与颜色 $\{\chi(G) + 1， \， \点，\，\chi(G) + \chi(G’)\}$．然后，给顶点上色 $H$从 $G$而且 $G’$相应的颜色 $\{1， \， \点，\，\chi(G) + \chi(G’)\}$．因为没有顶点 $G$而且 $G’$是相同的颜色，这构成了图形的着色 $H$,这意味着 $\chi(H) \le \chi(G) + \chi(G’)$．

现在，考虑一个最小的图着色 $H$．假设有 $n$顶点之间的颜色 $G$，假设有 $米$顶点之间的颜色 $G’$．因为每一个顶点 $G$是否与里面的每个顶点相邻 $G’$，两个顶点集不能有任何共同的颜色。所以这个图着色 $H$有准确的 $n + m$颜色。但是请注意, $通用电气\ n \气(G)$而且 $m \通用电气\气(G)$否则，色数将不是最小的(顶点的子图从 $G$在 $H$正是 $G$；同样, $G’$)．所以 $\chi(H) = n + m \ge \chi(G) + \chi(G’)$．

由此可见, $\chi(G) + \chi(G') = \chi(H)。$ $_ \广场$

的色多项式 $P_G$的图 $G$对每个自然数都是多项式吗 $k$，返回数字 $P_G (k)$的 $k$色素的 $G$． $\气(G)$最小的不是根的正整数是多少 $P_G$．的程度 $P_G$等于?的顶点数 $G$．

考虑一个无环图 $T_n$在 $n$顶点(也称为树)。证明 $P_{T_n}(k) = k (k-1)^{n-1}$．

---

考虑一个任意的顶点 $T_n$．有 $k$可能的颜色。现在，考虑它的每一个邻居;有 $k - 1$每种可能的颜色。然后，每个顶点的邻居也有 $k - 1$可能的颜色，等等。顶点的颜色不会有任何进一步的限制，因为图不包含任何周期．因此,有 $k$第一个顶点的选择 $k - 1$每个选项 $n - 1$随后的顶点;总共有 $P_{T_n}(k) = k (k-1)^{n-1}$选择。 $_ \广场$

用4种颜色正确的边着色

最常见的边着色类似于图(顶点)着色。图的每条边都有一个颜色，这样就不会有相邻的两条边是相同的颜色。这样的着色是一种适当的边缘着色．对于循环图，这种类比变成了等价，因为存在边-顶点对偶。然而，一般来说，色数与最小值无关 $k$这样就有了一条合适的边 $k$色素的存在。

另一种边缘着色是用在拉姆齐理论和类似的问题。在这种情况下，图的边是彩色的 $k$Colors和数学家研究得到的彩色图的子结构，以确定存在多少大小的完全子图。

最后一种边缘着色用于研究生成树．边缘着色的方式是这样的:不存在一个相同颜色的循环，对给定的图进行这种边缘着色所需的最小颜色数量被称为它的树性。

证明任何平面图的边着色最多为三种颜色，其中相同颜色的边允许相邻，但相同颜色的边不允许循环。

---

• 四色定理
• 图论
• 拉姆齐理论