The weighted coloring problem for two graph classes characterized by small forbidden induced structures

doi:10.1016/j.dam.2018.04.006

Discrete Applied Mathematics

Volume 247, 1 October 2018, Pages 423-432

https://doi.org/10.1016/j.dam.2018.04.006 Get rights and content

Under an Elsevier user license

open archive

Abstract

We show that the weighted coloring problem can be solved for ${P_{5}, b a n n e r}$ -free graphs and for ${P_{5}, d a r t}$ -free graphs in polynomial time on the sum of vertex weights.

Keywords

Computational complexity

Coloring problem

Hereditary class

Polynomial-time algorithm