Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs

Abstract

We give a $(1.796+\epsilon )$-approximation for the minimum sum coloring problem on chordal graphs, improving over the previous 3.591-approximation by Gandhi et al. [2005]. To do so, we also design the first polynomial-time approximation scheme for the maximum $k$-colorable subgraph problem in chordal graphs.

15 pages, preliminary version appeared in the proceedings of WADS 2023