Perfect colorings of the infinite square grid: coverings and twin colors

Perfect colorings of the infinite square grid: coverings and twin colors Full article

Journal

Electronic Journal of Combinatorics
ISSN: 1077-8926 , E-ISSN: 1097-1440

Output data

Year: 2023, Volume: 30, Number: 2, Article number : P2.4, Pages count : 59 DOI: 10.37236/10005

Funding (2)

1	Sobolev Institute of Mathematics	FWNF-2022-0017
2	Russian Foundation for Basic Research	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

Submitted:	Nov 8, 2020
Accepted:	Mar 20, 2023
Published print:	Apr 7, 2023
Published online:	Apr 7, 2023

Web of science:	WOS:000970966500001
Scopus:	2-s2.0-85151904363
Elibrary:	61823965
OpenAlex:	W3125859048

DB	Citing
Scopus	1