| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418885 | Discrete Applied Mathematics | 2014 | 7 Pages |
An edge-coloring of a graph GG with natural numbers is called a sum edge-coloring if the colors of edges incident to any vertex of GG are distinct and the sum of the colors of the edges of GG is minimum. The edge-chromatic sum of a graph GG is the sum of the colors of edges in a sum edge-coloring of GG. It is known that the problem of finding the edge-chromatic sum of an rr-regular (r≥3r≥3) graph is NPNP-complete. In this paper we give a polynomial time (1+2r(r+1)2)-approximation algorithm for the edge-chromatic sum problem on rr-regular graphs for r≥3r≥3. Also, it is known that the problem of finding the edge-chromatic sum of bipartite graphs with maximum degree 3 is NPNP-complete. We show that the problem remains NPNP-complete even for some restricted class of bipartite graphs with maximum degree 3. Finally, we give upper bounds for the edge-chromatic sum of some split graphs.
