边色数的分类问题及其有关性质

设图G为简单连通图,由Vizing定理可知△(G)≤x′(G)≤△(G)+1。其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(x)=△(G),则称G为第一类图,并记为G∈C~1;若x′(G)=△(G)+1,则称G为第二类图,记为G∈C~2。本文的目的在于讨论边色数的分类问题及其有关性