Том 22, номер 2, 2015 г., Стр. 17−26

УДК 519.718
В. Г. Визинг
О задачах раскраски для двухсезонных мультиграфов

Аннотация:
Предполагается, что есть два момента времени, называемых сезонами, в которых мультиграф может иметь различные множества рёбер. Такие мультиграфы с изменяющейся структурой называются двухсезонными. При раскраске вершин или рёбер каждый объект раскрашивается в одном сезоне. Приводятся оценки двухсезонного хроматического числа, описывается точный алгоритм минимальной раскраски рёбер двудольного двухсезонного мультиграфа.
Библиогр. 3.

Ключевые слова: двухсезонный мультиграф, двухсезонная раскраска.

DOI: 10.17377/daio.2015.22.470

Визинг Вадим Георгиевич ¹
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
е-mail: vizing@paco.net

Статья поступила 22 декабря 2014 г.
Исправленный вариант — 16 февраля 2015 г.

Литература

[1] Визинг В. Г. О базах вершин двухсезонного ориентированного графа // Докл. Одесского семинара по дискретной математике. 2014. № 15. С. 13–16.

[2] Garey M. R., Johnson D. S., Stockmeyer I. J. Some simplified NP-complete graph problems // Theoret. Comput. Sci. 1976. No. 1. P. 337–367.

[3] König D. Über Graphen und ihre Anvendung auf Determinantentheorie und Mengenlehre // Math. Ann. 1916. No. 77. P. 453–465.