QA438 : A new approach for solving minimum sum coloring problem and its generalization on simple graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > PhD > 2017
Authors:
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.
Keywords:
#vertex sum coloring #variable neighborhood search #holder set #holder and reducer set #vertex edge-difference chromatic sum #vertex edge-sum chromatic sum #non homomorphism theorems #fractional coloring #kneser graph Link
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: