International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 30, Pages 1563-1573

The chromatic sum of a graph: history and recent developments

Ewa Kubicka

Department of Mathematics, University of Louisville, Louisville 40292, KY, USA

Received 22 June 2003

Copyright © 2004 Ewa Kubicka. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.