色指数

色指数是对图的边进行合法着色所需的最少颜色数。合法的边着色要求共享端点的两条不同边颜色不同；它与要求相邻顶点颜色不同的顶点着色是两个问题。

定义与下界

设 $G$ 是有限简单无向图。最少边颜色数记为 ${\chi }^{\prime }(G)$，图的最大顶点度记为 $\Delta (G)$。同一个顶点连接的 $\Delta (G)$ 条边两两共享该顶点，必须使用不同颜色，因此 $${\chi }^{\prime }(G)\ge \Delta (G).$$ 没有边的图可约定色指数为零。

奇环与偶环

四环的边沿环依次交替使用红、蓝两色，首尾相接的边颜色也不同。因此 ${\chi }^{\prime }(C_4)=2=\Delta (C_4)$。

三角形的任意两条边都共享顶点，必须使用三种颜色，所以 ${\chi }^{\prime }(C_3)=3$，而最大度只有 2。更一般地，奇数长度的环无法只用两色：从第一条边开始交替，最后一条边会与第一条同色并在起点相邻。给其中一条边使用第三种颜色便可完成合法着色。偶环可以交替两色。因此 $${\chi }^{\prime }(C_n)=\{\begin{array}{cc}2,& n\ge 4\text{ 为偶数},\\ 3,& n\ge 3\text{ 为奇数}.\end{array}$$

四环可用两色；三角形的每一对边都相邻，需要三色。线型和颜色同时区分边的着色。

一般简单图

Vizing 定理指出，对有限简单图，色指数只能是 $\Delta$ 或 $\Delta +1$。因此最大度给出很紧的范围，但本身不决定取哪个值；上面的四环和三角形就是最大度均为 2、色指数却不同的例子。该定理的证明需要进一步构造，不由度数下界直接得出。

把原图每条边变为线图中的顶点，共享端点的边对应相邻顶点。因此原图的合法边着色，恰好对应线图的合法顶点着色： $${\chi }^{\prime }(G)=\chi (L(G)).$$ 公式中的 $\chi$ 是顶点色数。原图若允许多重边，色指数仍可定义，但不能未经核查就套用上面只针对简单图的两个可能值。