图的边覆盖染色中的分类问题

摘要

Let G be a graph with edge set E(G),S E(G) is called a edge cover of G if every vertex of G is an end vertex of an edge in S. The edge covering chromatic number of a graph G, denoted by χ′c(G), is the maximum size of a partition of E(G) into edge covers of G. It is known that for any graph G with minimum degree δ,δ-1≤X′c(G)≤δ. We say that G is of CI if χ′c(G)=δ, and that G is of CII if χ′c(G) =δ-1 for any graph G. Thus we can classify graphs into two types depending on the value of their edge covering chromatic numbers. In this paper,we consider the classification of planar graphs and balanced complete r-partite graphs.%设G是一个图,其边集是E(G),E(G)的一个子集S称为G的一个边覆盖,若G的每一点都是S中一条边的端点.G的一个(正常)边覆盖染色是对G的边进行染色,使得每一色组都是G的一个边覆盖,使G有(正常)边覆盖染色所需最多颜色数,称为G的边覆盖色数,用X'c(G)表示.已知的结果是对于任意简单图G,都有δ一1≤X'c(G)≤δ,δ是G的最小度.若X'c(G)=δ,则称G是CI类的;否则称为CII类的.本文主要研究了平面图及平衡的完全r分图的分类问题.