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

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

设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.