© Hindawi Publishing Corp. THE CHROMATIC SUM OF A GRAPH: HISTORY AND RECENT DEVELOPMENTS

The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength of a graph is the minimum number of colors necessary to obtain its chromatic sum. A natural generalization of chromatic sum is optimum cost chromatic partition (OCCP) problem, where the costs of colors can be arbitrary positive numbers. Existing results about chromatic sum, strength of a graph, and OCCP problem are presented together with some recent developments. The focus is on polynomial algorithms for some families of graphs and NP-completeness issues. 2000 Mathematics Subject Classification: 05C12, 05C05, 68Q25. 1. Introduction. Let G = (V,E) be a graph with a vertex set V and an edge set E. A proper coloring of the vertices of the graph G is assigning different colors to adjacent vertices. The chromatic number χ(G) is the smallest number of colors in a proper coloring of G. We start with two definitions which are central for this paper