Geodesic
Two-step colouring of grid graphs of different types
Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 3, pp. 166-180

Voir la notice de l'article provenant de la source Math-Net.Ru

In this article, we consider the NP-hard problem of the two-step colouring of a graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. The optimum two-step colouring is one that uses the minimum possible number of colours.The two-step colouring problem is studied in application to grid graphs. We consider four types of grids: triangular, square, hexagonal, and octogonal. We show that the optimum two-step colouring of hexagonal and octogonal grid graphs requires 4 colours in the general case. We formulate the polynomial algorithms for such a colouring. A square grid graph with the maximum vertex degree equal to 3 requires 4 or 5 colours for a two-step colouring. In the paper, we suggest the backtracking algorithm for this case. Also, we present the algorithm, which works in linear time relative to the number of vertices, for the two-step colouring in 7 colours of a triangular grid graph and show that this colouring is always correct. If the maximum vertex degree equals 6, the solution is optimum.
Keywords: two-step graph colouring, grid graph, triangular grid graph, square grid graph
Mots-clés : hexagonal grid graph, octogonal grid graph. 
@article{MAIS_2022_29_3_a1,
     author = {A. V. Smirnov},
     title = {Two-step colouring of grid graphs of different types},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {166--180},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2022_29_3_a1/}
}
TY  - JOUR
AU  - A. V. Smirnov
TI  - Two-step colouring of grid graphs of different types
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2022
SP  - 166
EP  - 180
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2022_29_3_a1/
LA  - ru
ID  - MAIS_2022_29_3_a1
ER  - 
%0 Journal Article
%A A. V. Smirnov
%T Two-step colouring of grid graphs of different types
%J Modelirovanie i analiz informacionnyh sistem
%D 2022
%P 166-180
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2022_29_3_a1/
%G ru
%F MAIS_2022_29_3_a1
A. V. Smirnov. Two-step colouring of grid graphs of different types. Modelirovanie i analiz informacionnyh sistem, Tome 29 (2022) no. 3, pp. 166-180. http://geodesic.mathdoc.fr/item/MAIS_2022_29_3_a1/