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

DOI10.37236/10005arXiv2010.15839MaRDI QIDQ6352593

Denis S. Krotov

Publication date: 29 October 2020

Abstract: 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. Keywords: perfect coloring, equitable partition, partition design, square grid, rectangular grid, wallpaper group, twin colors, graph covering

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Other designs, configurations (05B30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Perfect colorings of the infinite square grid: coverings and twin colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6352593)