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

Abstract

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 several classes of graphs, defined by forbidden induced subgraphs, such as (diamond, co-diamond)-free graphs.