Chromatic Index

定义（Definition）

chromatic index（图的边色数/边染色数）：在图论中，指把一个图的所有边用尽可能少的颜色着色，并且满足任意共享同一端点（相邻）的两条边颜色不同时，所需要的最少颜色数。常记作 χ′(G)。
（注：与“chromatic number（点色数/顶点染色数）”不同，chromatic index 讨论的是边而不是点。）

发音（Pronunciation, IPA）

/krəˈmætɪk ˈɪndeks/

例句（Examples）

The chromatic index of this simple graph is 3.
这个简单图的边色数是 3。

By Vizing’s theorem, the chromatic index of a simple graph is either equal to its maximum degree or one more than that.
根据维辛定理，一个简单图的边色数要么等于它的最大度数，要么比最大度数大 1。

词源（Etymology）

chromatic 来自希腊语 chroma，意为“颜色”，在数学里常借用来表示“着色/染色”。index 源自拉丁语 index，本义是“指示者、标记”，在学术语境中常指“指标/指数/数值”。合起来就是“（边）着色所需颜色数量的指标”。

相关词（Related Words）

• Chromatic Number
• Edge Coloring
• Vertex Coloring
• Vizing's Theorem
• Maximum Degree
• Class 1 Graph
• Class 2 Graph
• Line Graph

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

• Graph Theory — Reinhard Diestel（常在“Edge Colourings/边着色”相关章节讨论 χ′(G)）
• Introduction to Graph Theory — Douglas B. West（在边着色与定理应用部分使用 “chromatic index”）
• Graph Theory with Applications — J. A. Bondy & U. S. R. Murty（介绍边着色问题时使用该术语）