14 сентября 2018
Предметная область
Выходные данные
Ключевые слова
Вид публикации Статья
Контактные данные автора публикации ГОЛОВАЧ ПЕТР АЛЕКСАНДРОВИЧ, ПИНАР ХЕЕГЕРНЕС
Ссылка на публикацию в интернете


A graph is k-choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k-choosable for k > 3, and this problem is considered strictly harder than the k-coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P 5-free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k-coloring is still open on P 5-free graphs. To give a complete picture, we show that the problem remains NP-hard on P 5-free graphs when k is a part of the input.
Для того чтобы оставить комментарий необходимо авторизоваться.