International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 30, Pages 1563-1573
doi:10.1155/S0161171204306216
The chromatic sum of a graph: history and recent developments
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.
Abstract
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.