Graph-Coloring

定义 Definition

图着色（graph-coloring）是图论中的一个概念：给图的顶点（最常见）或边分配“颜色”（可理解为标签），使得相邻的顶点（或相邻的边）不出现相同颜色，并尽量使用最少的颜色数。最少需要的颜色数称为色数（chromatic number）。
（在不同语境下也可能指“边着色”等相关变体。）

发音 Pronunciation

/ˈɡræf ˈkʌlərɪŋ/

例句 Examples

Graph-coloring helps us schedule exams so that no student has two tests at the same time.
图着色可以帮助我们安排考试，确保任何学生不会在同一时间参加两场考试。

In computational complexity, deciding whether a graph-coloring with (k) colors exists is a classic NP-complete problem for many values of (k).
在计算复杂性理论中，判断一个图是否存在使用 (k) 种颜色的图着色，在许多 (k) 的取值下都是经典的 NP-完全问题。

词源 Etymology

该词由 graph（图） + color（着色） + -ing（名词化后缀）构成，字面意思是“对图进行着色”。其思想与著名的地图着色问题（如四色定理）密切相关：将地图区域视为顶点、相邻关系视为边，就得到图着色的抽象模型。

相关词 Related Words

• Chromatic
• Chromatic Number
• Vertex
• Edge
• Clique
• Bipartite
• Planar Graph
• Four-Color Theorem
• NP-Complete
• Constraint Satisfaction

文学与经典著作中的用例 Literary Works

• Introduction to Graph Theory（Bondy & Murty）：系统讲解图着色、色数等基础主题。
• Graph Theory（Reinhard Diestel）：在现代图论框架下讨论着色相关定理与方法。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：将图 (k)-着色作为经典 NP-完全问题条目之一。
• Algorithm Design（Kleinberg & Tardos）：在算法与近似算法语境中涉及图着色及其应用（如排课、资源分配）。
• Four Colors Suffice: How the Map Problem Was Solved（Robin Wilson）：以四色问题为主线，介绍与图着色相关的历史与思想。