О совершенных раскрасках цепей, кратных паросочетанию

О совершенных раскрасках цепей, кратных паросочетанию

Лисицына М. А., Августинович С. В.
Дискретный анализ и исследование операций, 29, 1, 33-45 (2022)
Скачать статью

УДК 519.174.7 
DOI: 10.33048/daio.2022.29.718

Аннотация:

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

Литература:
  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://www.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).

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0017).

Лисицына Мария Александровна
  1. Военная академия связи им. Маршала Советского Союза С. М. Буденного, 
    Тихорецкий пр., 3, 194064 Санкт-Петербург, Россия

E-mail: lisitsyna.mariya.mathematician@gmail.com

Августинович Сергей Владимирович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: avgust@math.nsc.ru

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

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.

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://www.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).