图的边覆盖染色中的分类问题(英文)  

THE CLASSIFICATION OF GRAPHS ON EDGE COVERING COLORING

作　　者：苗莲英[1] 逄世友[2] 

机构地区：[1]山东大学数学系,济南250100 [2]山东农业大学理学院,泰安271018

出　　处：《数学杂志》2001年第4期368-372,共5页Journal of Mathematics

基　　金：the National Natural Science Foundation and the Doctoral Foundationof the Education Committee of P.R.China

摘　　要：设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全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≤χ ′ 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.

关 键 词：边覆盖染色 CI类图 CII类图 完全r分图 简单图 

分 类 号：O157.5[理学—数学]