Том 24, номер 1, 2017 г., Стр. 21-30

УДК 519.8
Васильева Е. И., Пяткин А. В.
О предписанной $(k, l)$-раскраске инциденторов

Аннотация:
Правильная раскраска инциденторов называется $(k, l)$-раскраской, если разность цветов конечного и начального инциденторов лежит между $k$ и $l$. В предписанном варианте также требуется, чтобы цвет каждого инцидентора лежал в множестве допустимых цветов для данной дуги. Для того чтобы такая постановка имела смысл, считаем, что множество допустимых цветов каждой дуги представляет собой целочисленный интервал. Минимальная длина интервала, при которой предписанная $(k, l)$-раскраска инциденторов данного мультиграфа всегда существует, называется предписанным $(k, l)$-хроматическим числом. В статье доказываются оценки для предписанного $(k, l)$-хроматического числа мультиграфов степени 2 и 4.
Библиогр. 13.

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

DOI: 10.17377/daio.2017.24.542

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

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

Литература

[1] Визинг В. Г. Раскраска инциденторов мультиграфа в предписанные цвета // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 1. С. 32–39.

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

[3] Визинг В. Г. Жёсткая раскраска инциденторов в неориентированных мультиграфах // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 3. С. 48–53.

[4] Визинг В. Г. О $(p, q)$-раскраске инциденторов неориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 4. С. 23–39.

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

[6] Визинг В. Г., Пяткин А. В. Раскраска инциденторов мультиграфа // Topics in graph theory (R. I. Tyshkevich, ed.). 2013. С. 197–209.

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

[8] Пяткин А. В. $(k, l)$-Раскраска инциденторов кубических мультиграфов // Дискрет. анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 1. С. 49–53.

[9] Пяткин А. В. Некоторые верхние оценки для инциденторного $(k, l)$-хроматического числа // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, № 2. С. 66–78.

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

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

[12] Пяткин А. В. О предписанной раскраске инциденторов в мультиграфе степени 3 // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14, № 3. С. 80–89.

[13] Borodin O. V., Kostochka A. V.,Woodall D. R. List edge and list total colorings of multigraphs // J. Comb. Theory, Ser. B. 1997. V. 71, No. 2. P. 184–204.