Том 21, номер 3, 2014 г., Стр. 76-81

УДК 519.2+621.391
Пяткин А. В.
О мультираскраске рёбер унициклических графов

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

Ключевые слова: рёберная раскраска, мультираскраска, взвешенные графы, интервалы, задача open shop.

Пяткин Артем Валерьевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: artem@math.nsc.ru

Статья поступила 13 июня 2013 г.
Исправленный вариант — 24 июля 2013 г.

Литература

[1] Визинг В. Г. О мультираскраске вершин взвешенных графов // Дискрет. анализ и исслед. операций. Сер. 1. - 2007. - Т. 14, № 4. - С. 17–26.

[2] Визинг В. Г. О мультираскраске инциденторов взвешенного неориентированного мультиграфа // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 4. - С. 35–47.
Vizing V. G. Multicoloring the incidentors of a weighted undirected multigraph // J. Appl. Industr. Math. - 2012. - Vol. 6, N4. - P. 514-521.

[3] Shannon C. E. A theorem on coloring the lines of a network // J. Math. Phys. - 1949. - Vol. 28. - P. 148–151.

[4] Woeginger G. J. Open problems in the theory of scheduling // Bull. EATCS. - 2002. - N 76. - P. 67–83.