Том 13, серия 1, номер 4, 2006 г., Стр. 18-25

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

Аннотация:
Раскраска инциденторов ориентированного взвешенного мультиграфа называется допустимой, если:
а) примыкающие к одной вершине инциденторы окрашены в различные цвета;
б) разность между цветами конечного и начального инциденторов любой дуги не меньше веса этой дуги.
Оценивается снизу и сверху минимальное число цветов, необходимых для допустимой раскраски всех инциденторов мультиграфа $G$. Верхняя и нижняя оценки отличаются на $\lceil\Delta/2\rceil$, где $\Delta$ – степень мультиграфа $G$.
Библ. 3.

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

Статья поступила 10 июля 2006 г.