Sciact
  • EN
  • RU

Perfect colorings of the infinite square grid: coverings and twin colors Научная публикация

Журнал Electronic Journal of Combinatorics
ISSN: 1077-8926 , E-ISSN: 1097-1440
Вых. Данные Год: 2023, Том: 30, Номер: 2, Номер статьи : P2.4, Страниц : 59 DOI: 10.37236/10005
Ключевые слова perfect coloring, equitable partition, infinite square grid, infinite rectangular grid, graph covering, twin colors
Авторы Krotov D.S. 1
Организации
1 Sobolev Institute of Mathematics, Novosibirsk, Russia

Информация о финансировании (2)

1 Институт математики им. С.Л. Соболева СО РАН FWNF-2022-0017
2 Российский фонд фундаментальных исследований 20-51-53023

Реферат: A perfect coloring (equivalent concepts are equitable partition and partition design) of a graph G is a function f from the set of vertices onto some finite set (of colors) such that every node of color i has exactly S(i,j) neighbors of color j, where S(i,j) are constants, forming the matrix S called quotient. If S is an adjacency matrix of some simple graph T on the set of colors, then f is called a covering of the target graph T by the cover graph G. We characterize all coverings by the infinite square grid, proving that every such coloring is either orbit (that is, corresponds to the orbit partition under the action of some group of graph automorphisms) or has twin colors (that is, two colors such that unifying them keeps the coloring perfect). The case of twin colors is separately classified.
Библиографическая ссылка: Krotov D.S.
Perfect colorings of the infinite square grid: coverings and twin colors
Electronic Journal of Combinatorics. 2023. V.30. N2. P2.4 :1-59. DOI: 10.37236/10005 WOS Scopus РИНЦ OpenAlex
Даты:
Поступила в редакцию: 8 нояб. 2020 г.
Принята к публикации: 20 мар. 2023 г.
Опубликована в печати: 7 апр. 2023 г.
Опубликована online: 7 апр. 2023 г.
Идентификаторы БД:
Web of science: WOS:000970966500001
Scopus: 2-s2.0-85151904363
РИНЦ: 61823965
OpenAlex: W3125859048
Цитирование в БД:
БД Цитирований
Scopus 1
Альметрики: