Geodesic
On nonexistence of some perfect 2-colorings of Johnson graphs
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 52-68 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DA_2009_16_5_a5,
     author = {I. Yu. Mogilnykh},
     title = {On nonexistence of some perfect 2-colorings of {Johnson} graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {52--68},
     year = {2009},
     volume = {16},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_5_a5/}
}
TY  - JOUR
AU  - I. Yu. Mogilnykh
TI  - On nonexistence of some perfect 2-colorings of Johnson graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 52
EP  - 68
VL  - 16
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_5_a5/
LA  - ru
ID  - DA_2009_16_5_a5
ER  - 
%0 Journal Article
%A I. Yu. Mogilnykh
%T On nonexistence of some perfect 2-colorings of Johnson graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 52-68
%V 16
%N 5
%U http://geodesic.mathdoc.fr/item/DA_2009_16_5_a5/
%G ru
%F DA_2009_16_5_a5
I. Yu. Mogilnykh. On nonexistence of some perfect 2-colorings of Johnson graphs. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 52-68. http://geodesic.mathdoc.fr/item/DA_2009_16_5_a5/

[1] Mogilnykh I. Yu., “O regulyarnosti sovershennykh raskrasok grafa Dzhonsona v dva tsveta”, Probl. peredachi inform., 43:4 (2007), 37–44 | MR

[2] Fon-der-Flaas D. G., “Sovershennye 2-raskraski giperkuba”, Sib. mat. zhurn., 48:4 (2007), 923–930 | MR | Zbl

[3] Delsarte P., “An algebraic approach to the association schemes of coding theory”, Philips Res. Rep. Suppl., 10 (1973), 1–97 | MR

[4] Etzion T., Schwarz M., “Perfect constant-weight codes”, IEEE Trans. Inform. Theory, 50:9 (2004), 2156–2165 | DOI | MR

[5] Etzion T., “Configuration distribution and designs of codes in the Johnson scheme”, J. Combin. Designs, 15 (2007), 15–34 | DOI | MR | Zbl

[6] Etzion T., “On the nonexistence of perfect codes in the Johnson scheme”, SIAM J. Discr. Math., 9:2 (1996), 201–209 | DOI | MR | Zbl

[7] Gordon M. D., “Perfect single error-correcting codes in the Johnson scheme”, IEEE Trans. Inform. Theory, 52:10 (2006), 4670–4672 | DOI | MR

[8] Martin W. J., “Completely regular designs of strength one”, J. Alg. Combin., 3 (1994), 17–185 | DOI | MR

[9] Martin W. J., “Completely regular designs”, J. Combin. Designs, 6:4 (1998), 261–273 | 3.0.CO;2-D class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] Meyerowitz A., “Cycle–balanced partitions in distance-regular graphs”, Discr. Math., 264 (2003), 149–165 | DOI | MR | Zbl

[11] Mogilnykh I. Yu., Avgustinovich S. V., “Perfect 2-colorings of Johnson graphs $J(6,3)$ and $J(7,3)$”, Lect. Notes Comp. Sci., 5228, 2008, 11–19 | Zbl

[12] Mogilnykh I. Yu., Avgustinovich S. V., “Perfect colorings of Johnson graph in two colors”, Proc. of XI Intern. symposium on problems of redundancy in information and control systems (Saint-Petersburg, Russia, July 2–6, 2007), GUAP, SPb., 2007, 205–209

[13] Neumaier A., “Completely regular codes”, Discrete Math., 106/107 (1992), 353–360 | DOI | MR | Zbl