Том 12, серия 1, номер 4, 2005 г., Стр. 23-39

УДК 519.718
В. Г. Визинг
О $(p,q)$-раскраске инциденторов неориентированного мультиграфа

Аннотация:
Пусть $0\leqslant p\leqslant q$. Правильная раскраска инциденторов неориентированного мультиграфа называется $(p,q)$-раскраской, если для любого ребра модуль разности между цветами его инциденторов принадлежит интервалу $[p,q]$. Минимальное число цветов, необходимое для $(p,q)$-раскраски всех инциденторов мультиграфа $G$, называется $(p,q)$-хроматическим числом мультиграфа $G$ и обозначается через $\chi(p,q,G)$. При $p\geqslant 1$ для однородных мультиграфов $G$ степени $\Delta$ указываются точные значения $\chi(p,q,G)$ при всех $q\geqslant p$. Эти точные значения зависят только от $\Delta$ и не зависят от других структурных особенностей мультиграфов. Приводятся оценки $(p,q)$-хроматических чисел неоднородных мультиграфов.

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

Статья поступила 15 июля 2005 г.