Том 29, номер 1, 2022 г., Стр. 33-45

УДК 519.174.7
Лисицына М. А., Августинович С. В.
О совершенных раскрасках цепей, кратных паросочетанию

Аннотация:
Раскраска вершин графа $G$ называется совершенной, если цветовой состав окружения каждой вершины однозначно определяется цветом этой вершины. В работе дана полная характеризация совершенных раскрасок в произвольное конечное число цветов лексикографического произведения бесконечной цепи и паросочетания.
Ил. 1, библиогр. 18.

Ключевые слова: совершенная раскраска, бесконечная цепь, паросочетание, лексикографическое произведение.

DOI: 10.33048/daio.2022.29.718

Лисицына Мария Александровна ¹
Августинович Сергей Владимирович ²
1. Военная академия связи им. Маршала Советского Союза С. М. Буденного,
Тихорецкий пр., 3, 194064 Санкт-Петербург, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: lisitsyna.mariya.mathematician@gmail.com, avgust@math.nsc.ru

Статья поступила 7 июня 2021 г.
После доработки — 8 ноября 2021 г.
Принята к публикации 29 ноября 2021 г.

Литература

[1] Лисицына М. А., Августинович С. В. Совершенные раскраски призмы // Сиб. электрон. мат. изв. 2016. T. 13. С. 1116–1128.

[2] Taranenko A. A. Algebraic properties of perfect structures // Linear Algebra Appl. 2020. V. 607. P. 286–306.

[3] Lisitsyna M. A., Avgustinovich S. V., Parshina O. G. On perfect colorings of infinite multipath graphs // Сиб. электрон. мат. изв. 2020. Т. 17. С. 1863–1868.

[4] Хорошилова Д. Б. О циркулярных совершенных раскрасках в два цвета // Дискрет. анализ и исслед. операций. 2009. T. 16, № 1. С. 80–92.

[5] Хорошилова Д. Б. О параметрах совершенных 2-раскрасок циркулянтных графов // Дискрет. анализ и исслед. операций. 2011. T. 18, № 6. С. 82–89.

[6] Паршина О. Г. Совершенные 2-раскраски бесконечных циркулянтных графов со сплошным набором дистанций // Дискрет. анализ и исслед. операций. 2014. T. 21, № 2. С. 76–83.

[7] Parshina O. G., Lisitsyna M. A. The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances // Сиб. электрон. мат. изв. 2020. Т. 17. P. 590–603.

[8] Лисицына М. А., Паршина О. Г. Совершенные раскраски бесконечного циркулянтного графа с дистанциями 1 и 2 // Дискрет. анализ и исслед. операций. 2017. T. 24, № 3. С. 20–34.

[9] Axenovich M. A. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Math. 2003. V. 268, No. 1–3. P. 31–49.

[10] Пузынина С. А. Совершенные раскраски вершин графа $G(Z^2)$ в три цвета // Дискрет. анализ и исслед. операций. 2005. T. 12, № 1. С. 37–54.

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

[12] Пузынина С. А. Периодичность совершенных раскрасок бесконечной прямоугольной решётки // Дискрет. анализ и исслед. операций. 2004. T. 11, № 1. С. 79–92.

[13] Пузынина С. А. О периодичности совершенных раскрасок бесконечной гексагональной и треугольной решеток // Сиб. мат. журн. 2011. T. 52, №1. С. 115–132.

[14] Августинович С. В., Васильева А. Ю., Сергеева И. В. Дистанционно регулярные раскраски бесконечной квадратной решётки // Дискрет. анализ и исслед. операций. 2011. T. 18, № 3. С. 3–10.

[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). Novosibirsk: Sobolev Inst. Math., 2014. С. 98. Available at http://old.math.nsc.ru/conference/malmeet/14/Malmeet2014.pdf (accessed Jan. 28, 2022).

[16] Avgustinovich S. V., Krotov D. S., Vasil’eva A. Yu. Completely regular codes in the infinite hexagonal grid // Сиб. электрон. мат. изв. 2016. Т. 13. С. 987–1016.

[17] Plaksina V. D., Shcherbina P. A. New perfect colorings of infinite circulant graphs with continuous sets of distances // Сиб. электрон. мат. изв. 2021. Т. 18, № 1. С. 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. P. 80. Available at http://g2a2.imm.uran.ru/doc/G2A2_Abstracts.pdf (accessed Jan. 28, 2022).