关于近似二部图边覆盖染色的一个充分条件  

A sufficient condition on the edge covering coloring of nearly bipartite graphs

作　　者：王纪辉[1] 

机构地区：[1]山东大学数学与系统科学学院

出　　处：《山东大学学报（理学版）》2006年第1期21-23,共3页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(10471078);山东省自然科学基金资助项目(Y2003A01)

摘　　要：设G是一个简单图,其顶点集为V(G)而边集为E(G).S E(G)称为G的一个边覆盖,如果由S导出的子图是G的一个生成子图.G的边覆盖色数χc′(G)是E(G)所能划分成的最大边覆盖数.已知δ-1χc′(G)δ,由此将χc′(G)=δ的图称为CⅠ类图,否则称为CⅡ类图.显然,图的边覆盖染色分类问题是NP-完全的.给出了近似二部图是CⅠ类图的一个充分条件,而且该条件中的下界是最好的.Let G be a simple graph with vertex set V（G） and edge set E（G）. A subset S of E（G） is called an edge covering of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge coverings which construct a partition of E（G） is called the edge covered chromatic index of G, denoted by X＇c （G）. It is well known that 8 - 1 ≤X＇c （G） ≤δ, then G is called a graph of CⅠ class if X＇c （G） = δ, otherwise G is called a graph of C Ⅱ class. It is easy to prove that the problem of deciding whether a given graph is CⅠ class or CⅡ class is NP-complete. A sufficient condition for a nearly bipartite graph to be CⅠ class is given. It is showen that the results are the best possible.

关 键 词：近似二部图 边覆盖染色 最小度顶点 边覆盖色数 

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