维津定理

维津定理(Vizing theorem)是关于图的边着色的一个定理，若G是简单图，则Δ≤χ′(G)≤Δ+1，其中，Δ表示G上次最大的节点的次，χ′(G)表示边色数。这个定理是维津(V.G.Vizing)于1964年发表的，由此可以将简单图分为二类：对任意简单图G，若χ′(G)=Δ，则称G为第1类图；否则，称G为第2类图。