NP-Completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problem

This paper considers the two-step colouring problem for an undirected connected graph. The problem is about colouring the graph in a given number of colours so that no pair of vertices at a distance of 1 or 2 between each other has the same colour. Also the corresponding recognition problem is set. The problem is closely related to the classical graph colouring problem. In the article, the polynomial reduction of the problems to one another is analyzed and proved. In particular, this allows us to prove the NP-completeness of the two-step colouring problem. Also we specify some of its properties. The two-step colouring problem as applied to rectangular grid graphs is considered separately. The maximum vertex degree in these graphs ranges from 0 to 4. The function of two-vertex colouring in the minimum possible number of colours was defined and proved for each case. The resulting functions are drawn so that each vertex is coloured independently from others. If the vertices are examined in a sequence, the time for colouring a rectangular grid graph will be polynomial.