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

Abstract: 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.

Key words: edge covering coloring chromatic index , minimum degree vertex, edge covering coloring, nearly bipartite graph