Том 8, серия 1, номер 3, 2001 г., Стр. 3-14
УДК 519.74
В. Г. Визинг, Б. Тофт
Раскраска инциденторов и вершин неориентированного мультиграфа
Аннотация:
Понятия $p$-раскраски инциденторов и тотальной pp-раскраски, которые изучались ранее для ориентированных мультиграфов, распространяются на неориентированные мультиграфы. Изучается задача отыскания минимального числа цветов. Для раскраски инциденторов она решается точно; для тотальной раскраски в общем случае – приближенно с абсолютной погрешностью, не превышающей единицы, а в ряде частных случаев – точно.
Библиогр. 11.
Визинг В. Г. 1
Тофт Б. 2
1. 65070 Одесса, Украина
2. Оденсе, Дания
е-mail: vizing@paco.net, btoft@imada.sdu.dk
Статья поступила 10 мая 2001 г.
