Analysis of Greedy Algorithms for Chromatic Sum Coloring of a Graph

ABSTRACT Sum coloring of a graph is a vertex coloring using positive integers (colors) that minimizes the total sum of the colors assigned to all vertices, where adjacent vertices must have different colors. The chromatic sum is the smallest total among all proper colorings of the graph . The need for considering such a graph coloring model follows from its application to solve problems of scheduling equal length tasks (e.g., university timetables). It stems from the fact that finding a minimum chromatic sum coloring corresponds to finding a schedule that minimizes the mean flow time and total completion time of tasks. Unfortunately, evaluating is NP‐hard. Therefore, we are forced to use polynomial‐time approximation algorithms. In this article, we analyze four of the most popular greedy graph coloring algorithms: , , and , standing for Largest First , Smallest Last , Saturation Largest First ( DSatur ) and Greedy Independent Sets , along with their improvements adapted to the needs of chromatic sum coloring. For any such algorithm, we give its description, the smallest , that is, hard‐to‐color (for which the algorithm always yields a sum greater than ) and , that is, slightly hard‐to‐color (where a total sum of colors greater than is possible under the worst‐case vertex ordering) graphs, as well as an estimation of its computational complexity and performance function. Finally, we show that a certain 8‐vertex graph is for the whole collection of algorithms under consideration.