Abstarct: In this thesis, we mainly consider sum coloring problem which is very close to the classic coloring problem. This problem asks for the minimum possible summation of colors assigned properly to the vertices of a given graph. There are generally two different approaches dealing with this problem, which are namely analytic approach and algorithmic approach. To solve this problem, we introduce a mexta-heuristic method, categorized as in the second approach, which is called variable neighborhood search and is baxsed on a new structure of neighborhoods. To increase the speed of the neighborhood search process, we present some new definitions of holder vertex and set. Tested on $23$ commonly used benchmark instances, our algorithm shows acceptable competitive performance with respect to recently proposed heuristics. Moreover, the edge-difference chromatic sum and the edge-sum chromatic sum of graphs, as two generalizations of the chromatic sum, are introduced. In this regard, we present some necessary conditions for the existence of homomorphism between two graphs via these parameters. Furthermore, some upper and lower bounds for these parameters in terms of the fractional chromatic number, are introduced.