We give a (1.796+ε)-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.
No takes yet. Share an insight, caveat, or question.
DeHaan et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: