Том 16, номер 5, 2009 г., Стр. 52-68

УДК 621.391.15
И. Ю. Могильных
О несуществовании некоторых совершенных 2-раскрасок графов Джонсона

Аннотация:
Cовершенной раскраской в $m$ цветов вершин графа $G$ с матрицей $A=\{a_{ij}\}_{i,j=1,\dots,m}$ называется раскраска множества вершин графа $G$ в множество цветов $\{1,\dots,m\}$ такая, что число вершин цвета $j$, смежных с фиксированной вершиной цвета $i$, не зависит от выбора последней вершины и равно $a_{ij}$. В данной статье устанавливается нижняя оценка на параметр $a_{ij}$, $i\neq j$, совершенной раскраски графа Джонсона в два цвета. Также доказано несуществование некоторых совершенных раскрасок графов Джонсона в два цвета.
Библиогр. 13.

Ключевые слова: совершенная раскраска, полностью регулярный код, схема Джонсона.

Могильных Иван Юрьевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: ivmog84@gmail.com

Статья поступила 15 мая 2009 г.