Том 24, номер 4, 2017 г., Стр. 34-46

УДК 519.174
Головачёв М. О., Пяткин А. В.
Об (1, $l$)-раскраске инциденторов мультиграфов

Аннотация:
Доказано, что если $l$ больше или равно $\Delta/2 - 1$, то (1, $l$)-хроматическое число произвольного мультиграфа максимальной степени $\Delta$ не превосходит $\Delta + 1$. Кроме того, показано, что инциденторы любой ориентированной призмы можно раскрасить в четыре цвета так, чтобы любые два смежных инцидентора были раскрашены различно, а разность цветов конечного и начального инциденторов каждой дуги была равна 1.
Ил. 1, библиогр. 10.

Ключевые слова: раскраска инциденторов, (1, $l$)-раскраска, призма.

DOI: 10.17377/daio.2017.24.572

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

Статья поступила 22 марта 2017 г.
Исправленный вариант — 10 апреля 2017 г.

Литература

[1] Визинг В. Г. Двудольная интерпретация ориентированного мультиграфа в задачах раскраски инциденторов // Дискрет. анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 1. С. 27–41.

[2] Визинг В. Г. О линейных факторах мультиграфов // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, № 4. С. 3–7.

[3] Визинг В. Г., Мельников Л. С., Пяткин А. В. О (k, l)-раскраске инциденторов // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 4. С. 29–37.

[4] Пяткин А. В. Hекотоpые задачи оптимизации pасписания пеpедачи сообщений в локальной сети связи // Дискрет. анализ и исслед. опеpаций. 1995. Т. 2, № 4. С. 74–79.

[5] Пяткин А. В. Верхние и нижние оценки для инциденторного (k, l)-хроматического числа // Дискрет. анализ и исслед. операций. Сер. 1. 2004. Т. 11, № 1. С. 93–102.

[6] Пяткин А. В. Об (1, 1)-раскраске инциденторов мультиграфов степени 4 // Дискрет. анализ и исслед. операций. Сер. 1. 2004. Т. 11, № 3. С. 59–62.

[7] Diestel R. Graph theory. Heidelberg: Springer-Verl., 2016. (Grad. Texts Math.; Vol. 173).

[8] Mel’nikov L. S., Vizing V. G. The edge-chromatic number of a directed/mixed multigraph // J. Graph Theory. 1999. V. 23, No. 4. P. 267–273.

[9] Petersen J. Die Theorie der regulären Graphen // Acta Math. 1891. V. 15. P. 193–220.

[10] West D. B. Introduction to graph theory. Upper Saddle River: Prentice Hall, 2001.