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

设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Ⅰ类图的一个充分条件，而且该条件中的下界是最好的。

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

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 χ’c(G). It is well known that δ-1≤χ’c(G)≤δ , then G is called a graph of CⅠ class if χ’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. In this paper, we give a sufficient condition for a nearly bipartite graph to be CⅠclass. Furthermore we show that the results in this paper is the best possible.