Geodesic
Perfect colorings of submatrix hypergraphs
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 54-78 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A submatrix hypergraph $G_{n\times m}$ is a hypergraph whose vertices are entries of an ${n\times m}$ matrix and hyperedges are submatrices of order $2.$ In this paper, we consider perfect colorings of submatrix hypergraphs and study their parameters. We provide several constructions of perfect colorings of $G_{n\times m}$ and prove that the incidence matrices of $2$-designs are perfect colorings of the submatrix hypergraph. Moreover, we describe all perfect $2$-colorings of hypergraphs $G_{2\times m}$ and $G_{3\times m}.$ Illustr. 1, bibliogr. 12.
Keywords: hypergraph, symmetric 2-design, perfect coloring. 
@article{DA_2024_31_3_a2,
     author = {S. O. Borodin and A. A. Taranenko},
     title = {Perfect colorings of submatrix hypergraphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {54--78},
     year = {2024},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_3_a2/}
}
TY  - JOUR
AU  - S. O. Borodin
AU  - A. A. Taranenko
TI  - Perfect colorings of submatrix hypergraphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 54
EP  - 78
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_3_a2/
LA  - ru
ID  - DA_2024_31_3_a2
ER  - 
%0 Journal Article
%A S. O. Borodin
%A A. A. Taranenko
%T Perfect colorings of submatrix hypergraphs
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 54-78
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DA_2024_31_3_a2/
%G ru
%F DA_2024_31_3_a2
S. O. Borodin; A. A. Taranenko. Perfect colorings of submatrix hypergraphs. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 54-78. http://geodesic.mathdoc.fr/item/DA_2024_31_3_a2/

[1] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, N. V. Philips' Gloeilampenfabrieken, Eindhoven, 1973

[2] C. Godsil, “Compact graphs and equitable partitions”, Linear Algebra Appl., 255:1-3 (1997), 259–266 | DOI

[3] V. G. Vizing, “Distributive coloring of graph vertices”, Diskretn. Anal. Issled. Oper., 2:4 (1995), 3–12 (Russian)

[4] S. A. Puzynina, “Periodicity of perfect colorings of an infinite rectangular grid”, Diskretn. Anal. Issled. Oper., Ser. 1, 11:1 (2004), 79–92 (Russian)

[5] D. S. Krotov, “Perfect colorings of the infinite square grid: Coverings and twin colors”, Electron. J. Comb., 30:2 (2023), P2.4, 59 pp. | DOI

[6] M. A. Axenovich, “On multiple coverings of the infinite rectangular grid with balls of constant radius”, Discrete Math., 268:1-3 (2003), 31–49 | DOI

[7] S. V. Avgustinovich, I. Yu. Mogilnykh, “Perfect colorings of the John son graphs J(8,3) and J(8,4) with two colors”, J. Appl. Ind. Math., 5:1 (2011), 19–30 | DOI

[8] D. B. Khoroshilova, “On two-colour perfect colourings of circular graphs”, Diskretn. Anal. Issled. Oper., 16:1 (2009), 80–92 (Russian)

[9] Handbook of combinatorics, v. 1, Elsevier, Amsterdam, 1995, 2198 pp.

[10] V. N. Potapov, S. V. Avgustinovich, “Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs”, Sib. Math. J., 61:5 (2020), 867–877 | DOI

[11] A. A. Taranenko, Perfect colorings of hypergraphs, Cornell Univ., Ithaca, NY, 2022, 20 pp., arXiv: 2208.03447 | DOI

[12] Handbook of combinatorial designs, Chapman Hall/CRC, Boca Raton, 2007, 1018 pp.