Полная сложностная дихотомия для запрещенных подграфов с 7 ребрами в задаче о хроматическом индексе

Д. С. Малышев

?

Полная сложностная дихотомия для запрещенных подграфов с 7 ребрами в задаче о хроматическом индексе

Дискретный анализ и исследование операций. 2020. Т. 27. № 4. С. 104–130.

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

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое математика

Язык: русский

Полный текст

Ключевые слова: вычислительная сложность задача о рёберной раскраске сильно наследственный класс

Risk Assessment Models for Heated Tobacco Products

Maddalena L., Yildiz B., Del Vecchio Blanco F. и др., Risk Analysis 2026 Vol. 46 No. 4 P. 1–26

Добавлено: 22 сентября 2026 г.

Обобщение пространства Фока

Дильмухаметова Алия Мидхатовна, Напалков В. В., Муллабаева А. У., Уфимский математический журнал 2010 Т. 2 № 1 С. 52–58

В данной статье введены обобщённые пространства Фока и рассмотрены основные свойства этих пространств. Найдена операция, сопряженная к операции умножения на переменную в обобщенном пространстве Фока. Также определены собственные функции сопряженного оператора. Изучены обобщенное преобразование Лапласа и задача построения базиса для введенных пространств. ...