边着色

边着色（edge coloring）给图的边分配颜色；若任意两条有公共端点的不同边都使用不同颜色，就称为正常边着色。最少颜色数称为边色数或色指数，记为 ${\chi }^{\prime }(G)$。本文讨论有限无向简单图，无边图的边色数取零。

例如，边为 $ab,ac,bc,cd,de$ 时，可按此顺序分配颜色 $1,2,3,1,2$。顶点 $c$ 关联的三条边 $ac,bc,cd$ 分别使用二、三、一，互不冲突；边 $ab$ 与 $cd$ 不接触，因此可以复用颜色一。

数字和线色共同标记颜色类别。颜色可在没有公共端点的边上复用。

每个颜色类都是匹配

同一种颜色的边不能有公共端点，所以每个颜色类都是一个匹配。反过来，若把全部边划分成若干个匹配，并给每个匹配一种颜色，就得到正常边着色。因此边着色也就是将全部边分成尽量少的匹配。

若某顶点的度为 $\Delta$，它关联的 $\Delta$ 条边必须两两异色，故 $${\chi }^{\prime }(G)\ge \Delta (G).$$ 主例中 $\Delta =3$，已经给出三色方案，所以 ${\chi }^{\prime }=3$。下界不是对全部图都取等号：三角形最大度二，但三条边任意两条都接触，需要三色；四环却可沿环交替使用两色。

贪心构造与完整颜色上界

按任意固定次序逐边处理，每次选择在该边两个端点都未用过的最小正整数颜色。处理边 $uv$ 时，之前与它接触的边至多有 $$(\mathrm{deg}(u)-1)+(\mathrm{deg}(v)-1)\le 2\Delta -2$$ 条。它们禁止的不同颜色数不会超过边数，因此在 $1,2,\dots ,2\Delta -1$ 中总有可用颜色。这个计数证明算法不会卡住，并给出 $$\Delta \le {\chi }^{\prime }(G)\le 2\Delta -1(E\ne \varnothing ).$$ 算法不变量是已处理边始终正常着色：新边只取两个端点都空闲的颜色，故与全部已处理邻边均不冲突；其他边的颜色不改，旧有正常性保持。每轮处理一条新边，有限边数保证终止。

这个上界并不声称最优。简单图还有更强的 Vizing 定理 ${\chi }^{\prime }\le \Delta +1$，其证明需要调整已着色边，不能由上述直接贪心计数推出；本节给出的实现只保证 $2\Delta -1$ 上界。

可运行的Python实现

输入是无向边的二元组序列，端点须可用作字典键；不接受自环和重复无向边。返回与输入边次序一致的颜色列表，不改写输入。孤立顶点不参与任何边，故不需要单独列出。

Python 3

def greedy_edge_coloring(edges):
    edges = list(edges)
    used = {}
    seen = set()
    for u, v in edges:
        if u == v:
            raise ValueError("self-loop")
        key = frozenset((u, v))
        if key in seen:
            raise ValueError("duplicate undirected edge")
        seen.add(key)
        used.setdefault(u, set())
        used.setdefault(v, set())
    colors = []
    for u, v in edges:
        forbidden = used[u] | used[v]
        color = 1
        while color in forbidden:
            color += 1
        colors.append(color)
        used[u].add(color)
        used[v].add(color)
    return colors

main = [("a", "b"), ("a", "c"), ("b", "c"),
        ("c", "d"), ("d", "e")]
assert greedy_edge_coloring(main) == [1, 2, 3, 1, 2]
assert greedy_edge_coloring([]) == []
assert greedy_edge_coloring([(0, 1), (1, 2), (2, 0)]) == [1, 2, 3]
assert greedy_edge_coloring([(0, 1), (1, 2), (2, 3), (3, 0)]) == [1, 2, 1, 2]
for bad in [[(0, 0)], [(0, 1), (1, 0)]]:
    try:
        greedy_edge_coloring(bad)
    except ValueError:
        pass
    else:
        raise AssertionError("invalid input accepted")
print(greedy_edge_coloring(main))

若有 $m$ 条边、最大度 $\Delta \ge 1$，每轮合并两个颜色集合与查找可用颜色需 $O(\Delta )$ 次集合操作，通常哈希表均摊假设下总时间为 $O(m\Delta )$。所有端点记录的颜色数总计至多 $2m$，加上输入副本和结果列表，空间为 $O(n+m)$，其中 $n$ 是出现过的端点数。代码没有求出 $\Delta$，上界由正确性证明保证。

排班变式与图的条件

变式。 四叶星图的四条边都在中心相接，所以必须使用四种颜色，正好等于最大度四。若每条边表示两个人之间的一次会面、每种颜色表示一个时段，边着色就保证同一个人不会在一个时段参加两次会面；无公共参与者的会面可以同时进行。

图中若有自环，环同时接在同一点上，标准正常边着色一般不接受它。若允许多重边，上述贪心计数仍可用度数给出粗界，但 Vizing 的 $\Delta +1$ 上界不再直接适用。顶点着色要求的是相邻顶点异色，其色数也不应与本篇边色数混写。