Polynomial-time algorithms for minimum weighted colorings of ($P_5,{\bar{P}}_5$)-free graphs and related graph classes

Chính T. Hoàng, D. Adam Lazzarato

We design an $O(n^3)$ algorithm to find a minimum weighted coloring of a ($P_5,{\bar{P}}_5$)-free graph. Furthermore, the same technique can be used to solve the same problem for se…