Geodesic
On perfect colorings of paths divisible~by~a~matching
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 33-45.

Voir la notice de l'article provenant de la source Math-Net.Ru

A vertex coloring of a graph $G$ is called perfect if the color structure of the neighborhood of each vertex depends only on the color of this vertex. We give a complete characterization of perfect colorings with an arbitrary number of colors of the lexicographic product of the infinite path graph and the matching. Illustr. 1, bibliogr. 18.
Keywords: perfect coloring, infinite path graph, matching, lexicographic product.
Mots-clés : equitable partition 
@article{DA_2022_29_1_a2,
     author = {M. A. Lisitsyna and S. V. Avgustinovich},
     title = {On perfect colorings of paths divisible~by~a~matching},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {33--45},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a2/}
}
TY  - JOUR
AU  - M. A. Lisitsyna
AU  - S. V. Avgustinovich
TI  - On perfect colorings of paths divisible~by~a~matching
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 33
EP  - 45
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a2/
LA  - ru
ID  - DA_2022_29_1_a2
ER  - 
%0 Journal Article
%A M. A. Lisitsyna
%A S. V. Avgustinovich
%T On perfect colorings of paths divisible~by~a~matching
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 33-45
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a2/
%G ru
%F DA_2022_29_1_a2
M. A. Lisitsyna; S. V. Avgustinovich. On perfect colorings of paths divisible~by~a~matching. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 33-45. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a2/

[1] M. A. Lisitsyna, S. V. Avgustinovich, “Perfect colorings of the prism graph”, Sib. Elektron. Mat. Izv., 13 (2016), 1116–1128 (Russian)

[2] Taranenko A. A., “Algebraic properties of perfect structures”, Linear Algebra Appl., 607 (2020), 286–306

[3] M. A. Lisitsyna, S. V. Avgustinovich, O. G. Parshina,, “On perfect colorings of infinite multipath graphs”, Sib. Elektron. Mat. Izv., 17 (2020), 1863–1868

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

[5] D. B. Khoroshilova, “On the parameters of perfect $2$-colorings of circulant graphs”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 82–89 (Russian)

[6] O. G. Parshina, “Perfect $2$-colorings of infinite circulant graphs with continuous set of distances”, J. Appl. Ind. Math., 8:3 (2014), 357–361

[7] O. G. Parshina, M. A. Lisitsyna, “The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances”, Sib. Elektron. Mat. Izv., 17 (2020), 590–603

[8] M. A. Lisitsyna, O. G. Parshina, “Perfect colorings of infinite circulant graph with distances $1$ and $2$”, J. Appl. Ind. Math., 11:3 (2017), 381–388

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

[10] S. A. Puzynina, “Perfect colorings of vertices of the graph $G(Z^2)$ in three colors”, Diskretn. Anal. Issled. Oper., Ser. 2, 12:1 (2005), 37–54 (Russian)

[11] Krotov D. S., Perfect colorings of $Z^2$: Nine colors, Cornell Univ, Ithaca, NY, 2009, arXiv: 0901.0004

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

[13] S. A. Puzynina, “On periodicity of perfect colorings of the infinite hexagonal and triangular grids”, Sib. Math. J., 52:1 (2011), 91–104

[14] S. V. Avgustinovich, A. Yu. Vasil'eva, I. V. Sergeeva, “Distance regular colorings of the infinite rectangular grid”, J. Appl. Ind. Math., 6:3 (2012), 280–285

[15] Vasil'eva A. Yu., “Distance regular colorings of the infinite triangular grid”, Abs. Int. Conf. “Mal'tsev Meeting” (Novosibirsk, Russia, Nov. 10–13, 2014), Sobolev Inst. Math., Novosibirsk, 2014, 98 pp. (accessed Jan. 28, 2022) http://www.math.nsc.ru/conference/malmeet/14/Malmeet2014.pdf

[16] S. V. Avgustinovich, D. S. Krotov, A. Yu. Vasil'eva Completely regular codes in the infinite hexagonal grid, Sib. Elektron. Mat. Izv., 13 (2016), 987–1016

[17] V. D. Plaksina, P. A. Shcherbina, “New perfect colorings of infinite circulant graphs with continuous sets of distances”, Sib. Elektron. Mat. Izv., 18:1 (2021), 530–533

[18] Parshina O. G., “Perfect $k$-colorings of infinite circulant graphs with a continuous set of distances”, Abs. Int. Conf. PhD Summer School on Groups and Graphs, Algorithms and Automata (Yekaterinburg, Russia, Aug. 9–15, 2015), 2015, 80 pp. (accessed Jan. 28, 2022) http://g2a2.imm.uran.ru/doc/G2A2_Abstracts.pdf