图谱着色

图谱着色​是图谱标记的一个特例；它是对图谱中的元素进行传统上称为颜色的标签分配，并受到某些约束。在其最简单的形式中，它是一种为图的顶点着色的方法，使相邻的两个顶点不具有相同的颜色；这被称为顶点着色。同样，边着色为每条边分配颜色，使相邻的两条边不具有相同的颜色，而平面图的面着色为每个面或区域分配颜色，使共享边界的两个面不具有相同的颜色。顶点着色经常被用来介绍图形着色问题，因为其他着色问题可以转化为顶点着色实例。

图形着色的第一个结果几乎只涉及平面图形的地图着色。在试图为英格兰各郡的地图着色时，弗朗西斯-格思里提出了四色猜想，指出四种颜色足以为地图着色，从而使具有共同边界的区域都不会得到相同的颜色。格思里的弟弟将这个问题传给了他在大学学院的数学老师奥古斯都-德-摩根，后者在1852年给威廉-汉密尔顿的信中提到了这个问题。阿瑟-凯利在1879年伦敦数学会的一次会议上提出了这个问题。同年，阿尔弗雷德-肯普（AlfredKempe）发表了一篇论文，声称确立了这一结果，十年来，四色问题被认为已经解决。由于他的成就，肯普被选为皇家学会会员，后来又被选为伦敦数学学会主席。1890年，海伍德指出肯普的论点是错误的。然而，在那篇论文中，他证明了五色定理，说每个平面图都可以用不超过五种颜色来着色，使用的是肯普的想法。在接下来的一个世纪里，大量的工作和理论被开发出来，以将颜色的数量减少到四种，直到四色定理最终在1976年被KennethAppel和WolfgangHaken证明。该证明回到了Heawood和Kempe的想法，并在很大程度上无视了中间的发展。四色定理的证明还值得一提的是，它是第一个重要的计算机辅助证明。1912年，乔治-大卫-伯克霍夫引入色度多项式来研究着色问题，被图特概括为图特多项式，是代数图论的重要结构。

Kempe在1879年已经引起了对一般的、非平面的情况的注意，在20世纪初，许多关于平面图着色对高阶表面的泛化的结果也随之而来。1960年，ClaudeBerge提出了另一个关于图形着色的猜想，即强完美图形猜想，最初的动机是香农提出的一个称为图形零误差容量的信息论概念。这个猜想40年来一直没有得到解决，直到2002年被Chudnovsky、Robertson、Seymour和Thomas确立为著名的强完美图定理。自20世纪70年代初以来，图形着色一直被作为一个算法问题来研究：色度数问题（见下文）是Karp在1972年提出的21个NP-complete问题之一，大约在同一时期，基于回溯和Zykov（1949）的删除-收缩递归的各种指数时间算法被开发出来。图着色的主要应用之一，即编译器中的寄存器分配，于1981年被引入。

一个图的边着色只是其线图的一个顶点着色，而一个平面图的面着色只是其对偶的一个顶点着色。然而，非顶点着色问题往往是按原样陈述和研究的。这一方面是教学上的原因，另一方面是因为有些问题最好以非顶点形式来研究，如边缘着色的情况。使用颜色的惯例起源于为地图的国家着色，其中每个面都是字面上的颜色。这被概括为对嵌入平面的图形的面进行着色。通过平面二重性，它变成了给顶点着色，而在这种形式下，它可以推广到所有的图形。在数学和计算机表示中，典型的做法是使用前几个正整数或非负整数作为颜色。一般来说，人们可以使用任何有限集作为颜色集。着色问题的性质取决于颜色的数量，但不取决于它们是什么。图谱着色享有许多实际应用和理论上的挑战。除了经典的问题类型外，还可以对图形、分配颜色的方式、甚至是颜色本身设置不同的限制。它甚至以流行的数字谜题"数独"的形式在公众中流行起来。图形着色仍然是一个非常活跃的研究领域。