2024/06/27 by DeHaan, Ian, Friggstad, Zachary
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2406.18835
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.