• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

О сложности задачи вершинной 3-раскраске для наследственных классов графов, определяемых запретами небольшого размера

Задача о 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем 5 вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не более чем 5 вершинами, и для всех соответствующих наследственных классов, кроме трёх, устанавливается вычислительный статус задачи о 3-раскраске. Для двух из трёх оставшихся случаев доказывается полиномиальная эквивалентность и полиномиальная сводимость к третьему.