On sum coloring of graphs Original Research Article

The sum coloring problem asks to find a vertex coloring of a given graph G, using natural numbers, such that the total sum of the colors is minimized. A coloring which achieves this total sum is called an optimum coloring and the minimum number of colors needed in any optimum coloring of a graph is called the strength of the graph. We prove the NP-hardness of finding the vertex strength for graphs with Δ=6. Polynomial time algorithms are presented for the sum coloring of chain bipartite graphs and k-split graphs. The edge sum coloring problem and the edge strength of a graph are defined similarly. We prove that the edge sum coloring and the edge strength problems are both NP-complete for k-regular graphs, k⩾3. Also we give a polynomial time algorithm to solve the edge sum coloring problem on trees.