
_START_ARTICLE_
Vizing定理
_START_PARAGRAPH_
Vizing定理是图论中的定理。它描述了边着色数与度的关系。
_START_SECTION_
定理陈述
_START_PARAGRAPH_
Vizing定理：任意(简单, 无向)图 G 的边着色数(edge chromatic number, χ′(G)) 等于 Δ(G) 或 Δ(G) + 1，其中 Δ(G) 指图G 中最大的度。