图着色

图着色将标签或颜色分配给图的元素，使得相邻元素颜色不同，并研究所需的最少颜色数量。

Definition

图的恰当着色是指为其顶点分配颜色，使得任意两个相邻顶点不共享同一颜色；色数是存在这种分配所需的最少颜色数量。

Scope

本主题探讨了恰当顶点着色和色数、边着色和色指数、计算着色数的色多项式，以及包括布鲁克斯定理、维津定理和平面图四色定理在内的里程碑式成果。它将着色与独立集、团和更广泛的图参数理论联系起来。

Core questions

• 给定图的恰当着色需要的最少颜色数量是多少？
• 一个图在给定调色板下有多少种恰当着色方式？
• 哪些图可以用少量颜色着色，哪些障碍会强制使用大量颜色？
• 边着色和列表着色如何扩展基本概念？

Key concepts

• 恰当顶点着色
• 色数
• 色多项式
• 边着色和色指数
• 布鲁克斯定理
• 四色定理

Key theories

四色定理

任何平面图都可以用最多四种颜色进行恰当着色，这个命题悬而未决一个多世纪，并于1976年由阿佩尔和哈肯通过广泛的计算机辅助案例分析首次证明。

维津定理

任何简单图的边都可以用最大度数或最大度数加一的颜色进行恰当着色，将所有图分为两个狭窄的类别。

Clinical relevance

着色模拟了无冲突的资源分配：无冲突调度、编译器中的寄存器分配、无线网络中的频率分配以及数独式约束问题都可以归结为图着色问题。

History

1852年提出的四色猜想推动了着色理论的很大一部分发展；1976年阿佩尔和哈肯通过计算机辅助证明是计算机辅助数学的早期里程碑，并引发了关于证明本质的辩论。

Debates

计算机辅助证明的地位

四色定理对机器验证案例的依赖提出了一个问题：一个长到人类无法手动验证的证明是否应被视为真正的数学证明。

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

图的色数是多少？

它是使相邻顶点总是获得不同颜色所需的最少颜色数量；例如，奇数环的色数为三。

四色定理适用于所有地图吗？

它适用于绘制在平面或球体上且区域连通的地图；在环面等曲面上的地图可能需要更多颜色。