Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
Ian DeHaan, Zachary Friggstad · arXiv (Cornell University) · 2024
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.