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

Статья

Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов

Дискретная математика. 2016. Т. 28. № 2. С. 44-50.

Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, определяемых запрещёнными подграфами, каждый из которых имеет не более 6 рёбер или не более 7 вершин.