Classification of regular graphs of three-point sets

V. V. Promyslov

Lomonosov Moscow State University

Abstract: A regular graph of the ring of matrices over a field is a graph on the set of invertible matrices. Two matrices are connected with an edge if and only if their sum is singular. One of the questions in this field is whether the chromatic number of this graph is finite or not. This question was first formulated in 2009 at the 22nd British Conference on Combinatorics. It remains open for the fields of the characteristic 0. To investigate this issue in the article [4] was introduced a definition of a regular graph of a set. The regular graph of a set generalizes the concept of the regular graph of the matrix ring. There is a close connection between these concepts. For example, if the chromatic number of a regular graph of a circle on the Euclidean plane is infinite, then so will be the chromatic number of a regular graph of the matrix ring of order higher than two. In this paper, we investigate the structure of regular graphs of sets of three elements and classify the graphs up to isomorphism.

Keywords: regular graph of the matrix ring, classification of graphs up to isomorphism.