Volume 29, No 1, 2022, P. 33-45

UDC 519.174.7
M. A. Lisitsyna and S. V. Avgustinovich
On perfect colorings of paths divisible by a matching

Abstract:
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, equitable partition, infinite path graph, matching, lexicographic product.

DOI: 10.33048/daio.2022.29.718

Maria A. Lisitsyna ¹
Sergey V. Avgustinovich ²
1. Budyonny Military Academy of the Signal Corps,
3 Tikhoretsky Avenue, 194064 St. Petersburg, Russia
2. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: lisitsyna.mariya.mathematician@gmail.com, avgust@math.nsc.ru

Received June 7, 2021
Revised November 8, 2021
Accepted November 29, 2021

References

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

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

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

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

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

[6] O. G. Parshina, Perfect 2-colorings of infinite circulant graphs with continuous set of distances, Diskretn. Anal. Issled. Oper. 21 (2), 76–83 (2014) [Russian] [J. Appl. Ind. Math. 8 (3), 357–361 (2014)].

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

[8] M. A. Lisitsyna and O. G. Parshina, Perfect colorings of infinite circulant graph with distances 1 and 2, Diskretn. Anal. Issled. Oper. 24 (3), 20–34 (2017) [Russian] [J. Appl. Ind. Math. 11 (3), 381–388 (2017)].

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

[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), 37–54 (2005) [Russian].

[11] D. S. Krotov, Perfect colorings of $Z^2$: Nine colors (Cornell Univ., Ithaca, NY, 2009) (Cornell Univ. Libr. e-Print Archive, arXiv:0901.0004).

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

[13] S. A. Puzynina, On periodicity of perfect colorings of the infinite hexagonal and triangular grids, Sib. Mat. Zh. 52 (1), 115–132 (2011) [Russian] [Sib. Math. J. 52 (1), 91–104 (2011)].

[14] S. V. Avgustinovich, A. Yu. Vasil’eva, and I. V. Sergeeva, Distance regular colorings of the infinite rectangular grid, Diskretn. Anal. Issled. Oper. 18 (3), 3–10 (2011) [Russian] [J. Appl. Ind. Math. 6 (3), 280–285 (2012)].

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

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

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

[18] O. G. Parshina, Perfect k-colorings of infinite circulant graphs with a continuous set of distances, in Groups and Graphs, Algorithms and Automata (Abs. Int. Conf. PhD Summer Sch., Yekaterinburg, Russia, Aug. 9–15, 2015) (Ural. Fed. Univ., Yekaterinburg, 2015), p. 80. Available at http://g2a2.imm.uran.ru/doc/G2A2_Abstracts.pdf (accessed Jan. 28, 2022).