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

Статья

О количестве граничных классов в задаче о 3-раскраске

Дискретная математика. 2009. Т. 21. № 4. С. 129-134.

Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске.