Том 14, серия 1, номер 2, 2007 г., Стр. 3-15
УДК 519.718
В. Г. Визинг, А. В. Пяткин
Об оценках инциденторного хроматическогочисла взвешенного неориентированного мультиграфа
Аннотация:
Правильная раскраска инциденторов неориентированного взвешенного мультиграфа называется допустимой, если модуль разности между цветами инциденторов каждого ребра не меньше веса этого ребра. Наименьшее число цветов, необходимое для допустимой раскраски инциденторов, называется инциденторным хроматическим числом мультиграфа. Исследуется задача отыскания этого числа. Доказана NP-трудность этой задачи для$\Delta$ цветов. Найдены верхние и нижние оценки для инциденторного хроматического числа.
Библ. 5.
В. Г. Визинг 1
А. В. Пяткин 2
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
2. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: vizing@paco.net, vizing@paco.net
Статья поступила 8 ноября 2006 г.
