Предметная область | — |
Выходные данные | — |
Ключевые слова | — |
Вид публикации | Статья |
Контактные данные автора публикации | ГОЛОВАЧ ПЕТР АЛЕКСАНДРОВИЧ, ПИНАР ХЕЕГЕРНЕС |
Ссылка на публикацию в интернете | elibrary.ru/item.asp?id=21126752 |
Аннотация
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.
ПодробнееДля того чтобы оставить комментарий необходимо авторизоваться.