• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 27 публикаций
Сортировка:
по названию
по году
Статья
Vyalyi M., Tarasov S. Discrete Applied Mathematics. 2008. Vol. 156. P. 2070-2078.
Добавлено: 17 октября 2014
Статья
Kuznetsov S., Obiedkov S. Discrete Applied Mathematics. 2008. Vol. 156. No. 11. P. 1994-2003.
Добавлено: 6 марта 2009
Статья
Gribanov D., Malyshev D. Discrete Applied Mathematics. 2017. Vol. 227. P. 13-20.
Добавлено: 23 апреля 2017
Статья
Malyshev D. Discrete Applied Mathematics. 2018. Vol. 247. P. 423-432.
Добавлено: 23 апреля 2018
Статья
Malyshev D., Lobanova O. O. Discrete Applied Mathematics. 2017. Vol. 219. P. 158-166.
Добавлено: 21 ноября 2016
Статья
Lozin V. V., Malyshev D. Discrete Applied Mathematics. 2017. Vol. 216. P. 273-280.

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.

Добавлено: 3 марта 2015
1 2