论文部分内容阅读
设图G(V,E)是简单图，其中V(G)和E(G)是图的顶点集和边集，设C是边集E到集合{1，2，…，κ)的映射，即C：E→{1，2，…，κ}，称C是图G的κ-边染色。令Cv-1(I)为图G在染色C中与顶点v关联的I色边的数目。若对V中每个顶点v及每种颜色I∈{1，2，…，κ}都有Gv-1(I)≥1成立，则称C为图G的边覆盖染色。使G有边覆盖染色所需最大κ称为G的边覆盖色数，用Xc(G)表示．已知δ-1≤Xc(G)≤δ，由此将Xc(G)=δ的图称为CI类图，否则称为CII类图，显然图的边覆盖染色分类问题是NP-完全的。讨论了基于边覆盖色数的完全三部图的分类问题，得到了完全三部图为CI类图的充要条件。