RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2010, том 7, страницы 65–75 (Mi semr228)

Эта публикация цитируется в 8 статьях

Статьи

О совершенных $2$-раскрасках гиперкуба

К. В. Воробьёвa, Д. Г. Фон-дер-Флаассb

a Новосибирский государственный университет
b Институт математики им. С. Л. Соболева СО РАН

Аннотация: A vertex coloring of a graph is called perfect if the multiset of colors appearing on the neighbours of any vertex depends only on the color of the vertex. The parameters of a perfect coloring are thus given by a $n\times n$ matrix, where $n$ is the number of colors.
We give a recursive construction which can produce many different perfect colorings of the hypercube $H_n$ with $2$ colors and the parameters $\left({
\begin{array}{ll} a & b\\c & d \end{array}
}\right)$ satisfying the conditions $({b,c})=1,b+c=2^m$, $c>1$. In particular, this construction allows one to find many non-isomorphic perfect colorings with the parameters $\left( {
\begin{array}{ll} k\cdot a & k\cdot b\\k\cdot c & k\cdot d \end{array}
}\right)$. For the parameters $\left({
\begin{array}{ll} a & b\\c & d \end{array}
}\right)$ satisfying the extra condition $a\ge c-({b,c})$, we find a lower bound on the number of produced colorings which is hyperexponential in $n$.

Ключевые слова: homogenization, nonlinear diffusion, compressible viscous fluid.

УДК: 517.95

MSC: 76S05

Поступила 22 декабря 2009 г., опубликована 10 марта 2010 г.



Реферативные базы данных:


© МИАН, 2024