Volume 16, No 5, 2009, P. 52-68

UDC 621.391.15
I. Yu. Mogilnykh
On nonexistence of some perfect 2-colorings of Johnson graphs

Abstract:
A perfect coloring in $m$ colors of a graph $G$ with matrix $A=\{a_{ij}\}_{i,j=1,\dots,m}$ is a coloring of vertex set of $G$ in the set of colors $\{1,\dots,m\}$ such that the number of vertices of color $j$ adjacent to a fixed vertex of color $i$ does not depend on choice of the last vertex and equals $a_{ij}$. In this paper we obtain a low bound on parameter $a_{ij}$, $i\neq j$, of a perfect coloring of a Johnson graph in two colors. Also we show that some perfect colorings of Johnson graph in two colors do not exist.
Bibl. 13.

Keywords: perfect coloring, completely regular code, Johnson scheme.

Mogilnykh Ivan Yur'evich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: ivmog84@gmail.com