#### Title:

On sum edge-coloring of regular, bipartite and split graphs

#### Author:

#### Type:

#### Co-author(s) :

#### Uncontrolled Keywords:

Edge-coloring ; Sum edge-coloring ; regular graph ; bipartite graph ; Split graph

#### Abstract:

An edge-coloring of a graph G with natural numbers is called a sum edge-coloring if the colors of edges incident to any vertex of G are distinct and the sum of the colors of the edges of G is minimum. The edge-chromatic sum of a graph G is the sum of the colors of edges in a sum edge-coloring of G. It is known that the problem of finding the edge-chromatic sum of an r-regular (r≥3) graph is NP-complete. In this paper we give a polynomial time (1+2r(r+1)2)-approximation algorithm for the edge-chromatic sum problem on r-regular graphs for r≥3. Also, it is known that the problem of finding the edge-chromatic sum of bipartite graphs with maximum degree 3 is NP-complete. We show that the problem remains NP-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.

#### Publisher:

#### Date submitted:

#### Date accepted:

#### Date of publication:

#### DOI:

#### ISSN:

#### Language:

#### Journal or Publication Title:

#### Volume:

#### URL:

#### Affiliation:

Institute for Informatics and Automation Problems ; Russian-Armenian State University ; Department of Applied Mathematics and Informatics