Том 11, серия 1, номер 1, 2004 г., Стр. 93-102

УДК 519.172
А. В. Пяткин
Верхние и нижние оценки для инциденторного $(k,l)$-хроматического числа

Аннотация:
Исследуется минимальное число цветов, достаточное для $(k,l)$-раскраски инциденторов любого мультиграфа степени $\Delta$ при разных значениях $k$ и $l$. Доказано, что для мультиграфа степени $\Delta$ и $l=\lceil\Delta/2\rceil$ это число не превосходит $\Delta +k$. Кроме того, для всякого нечетного $\Delta$ построена бесконечная серия мультиграфов степени $\Delta$, $(1,1)$-хроматическое число которых больше $\Delta +1$.

Пяткин А. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 21 августа 2003 г.