Том 10, серия 1, номер 1, 2003 г., Стр. 14-40

УДК 519.172
В. Г. Визинг
Интервальная раскраска инциденторов неориентированного мультиграфа

Аннотация:
Раскраска инциденторов неориентированного мультиграфа называется интервальной $p$-раскраской, если a) инциденторы раскрашены правильно; b) ребра $p$-раскрашены, т.е. модуль разности между цветами инциденторов одного и того же ребра не меньше $p$; c) множество цветов инциденторов при каждой вершине представляет собой интервал. Наименьшее число цветов, необходимое для интервальной $p$-раскраски всех инциденторов мультиграфа, называется интервальным $p$-хроматическим числом. Приводятся нижние и верхние оценки, а в некоторых случаях указываются точные значения интервального $p$-хроматического числа.
Библиогр. 11.

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

Статья поступила 13 ноября 2002 г.