A sufficient condition on the edge covering coloring of nearly bipartite graphs
Jihui Wang · Journal of Shandong University · 2006
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.A sufficient condition for a nearly bipartite graph to be CⅠclass is given.It is showen that the results are the best possible.