On The Sum (multi-) Coloring Problem On (Proper) Interval Graphs

The sum (Multi-)coloring Problem have many applications. The sum coloring (SC) problem asks to find a vertex coloring of a given graph G , such that the total sum of the colors is minimized. The sum Multi-coloring (SMC) problem: Given a graph and the number of colors required by each vertex, find a multi-coloring which minimizes the sum of the largest colors assigned to the vertices. This paper proved that the MAXIS algorithm is a 2-approximation to the SC of proper interval graphs with Bounded Degree and α(G) ≤ ω(G) . where α(G) is the maximum degree of vertices of graph, n is the number of vertices of graph. And we describe a MAXCL algorithm to find a trivial lower bound for the chromatic sum on an arbitrary interval graph. Moreover, We extend LB algorithm to the weighted proper interval graphs, and show that a 4-approximation algorithm can be obtained to the SMC of proper interval graphs.