Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




2023-ary quasigroups and related topics
October 30, 2020 11:00–12:15, Novosibirsk, online
 


Bipartite perfect colorings of the infinite square grid: twin colors and the covering case

D. S. Krotov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Number of views:
This page:170

Abstract: A perfect coloring ( equitable partition) 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 adjacent 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 when the target graph is bipartite, 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 whose identifying keeps the perfectness of the coloring). The case of twin colors is separately classified.

Language: Russian or English if preferred by participants
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024