Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа

Правильная раскраска инциденторов неориентированного взвешенного мультиграфа называется допустимой, если модуль разности между цветами инциденторов каждого ребра не меньше веса этого ребра. Наименьшее число цветов, необходимое для допустимой раскраски инциденторов, называется инциденторным хроматическим числом мультиграфа. Исследуется задача отыскания этого числа. Доказана NP-трудность этой задачи для $\Delta$ цветов. Найдены верхние и нижние оценки для инциденторного хроматического числа.