图形着色和着色数

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

一个图着色是给a的顶点分配一个叫做颜色的标签吗图使两个相邻的顶点不具有相同的颜色。的彩色数字 $\气(G)$的图 $G$是最小的可以为其赋值的颜色数。图表上也存在其他类型的着色，最明显的是边缘色素这可能会受到各种限制。

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

这个图表不是两色的这个图是3色的这个图是四色的

图的色数是图可以着色的最小颜色数。这个定义有点微妙，因为它通常不是直接什么最小的数量是多少。对于某些类型的图，例如complete ( $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{cases} 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， \， \dots， \， \chi(G)\}$和 $G’$有一个用颜色着色的图表吗 $\{chi(G) + 1， \， \点，\，\chi(G) + \chi(G')\}$．然后，给顶点着色 $H$从 $G$和 $G’$相应的颜色 $\{1， \， \dots， \， \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$颜色和数学家研究得到的彩色图子结构，以确定完全子图存在的大小。

最后一种类型的边着色是用于研究生成树．边的着色方式是这样的，即不存在一个相同颜色的循环，并且给定图的这种边着色所需要的颜色的最小数量被称为它的树状度。

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

---

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