Geodesic
NP-completeness and one polynomial subclass of the two-step graph colouring problem
Modelirovanie i analiz informacionnyh sistem, Tome 26 (2019) no. 3, pp. 405-419 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we study the two-step colouring problem for an undirected connected 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. Also the corresponding recognition problem is set. The problem is closely related to the classical graph colouring problem. In the article, we study and prove the polynomial reduction of the problems to each other. So it allows us to prove NP-completeness of the problem of two-step colouring. Also we specify some of its properties. Special interest is paid to the problem of two-step colouring in application to rectangular grid graphs. The maximum vertex degree in such a graph is between 0 and 4. For each case, we elaborate and prove the function of two-vertex colouring in the minimum possible number of colours. The functions allow each vertex to be coloured independently from others. If vertices are examined in a sequence, colouring time is polynomial for a rectangular grid graph.
Keywords: two-step graph colouring, NP-completeness, grid graph, rectangular grid graph. 
@article{MAIS_2019_26_3_a5,
     author = {N. S. Medvedeva and A. V. Smirnov},
     title = {NP-completeness and one polynomial subclass of the two-step graph colouring problem},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {405--419},
     year = {2019},
     volume = {26},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2019_26_3_a5/}
}
TY  - JOUR
AU  - N. S. Medvedeva
AU  - A. V. Smirnov
TI  - NP-completeness and one polynomial subclass of the two-step graph colouring problem
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2019
SP  - 405
EP  - 419
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MAIS_2019_26_3_a5/
LA  - ru
ID  - MAIS_2019_26_3_a5
ER  - 
%0 Journal Article
%A N. S. Medvedeva
%A A. V. Smirnov
%T NP-completeness and one polynomial subclass of the two-step graph colouring problem
%J Modelirovanie i analiz informacionnyh sistem
%D 2019
%P 405-419
%V 26
%N 3
%U http://geodesic.mathdoc.fr/item/MAIS_2019_26_3_a5/
%G ru
%F MAIS_2019_26_3_a5
N. S. Medvedeva; A. V. Smirnov. NP-completeness and one polynomial subclass of the two-step graph colouring problem. Modelirovanie i analiz informacionnyh sistem, Tome 26 (2019) no. 3, pp. 405-419. http://geodesic.mathdoc.fr/item/MAIS_2019_26_3_a5/

[1] Korsakov S. V., Smirnov A. V., Sokolov V. A., “Principles of Organizing the Interoperability of Equipollent Nodes in a Wireless Mesh-Network with Time Division Multiple Access”, Automatic Control and Computer Sciences, 50:6 (2016), 415–422 | DOI

[2] Harary F., Graph theory, Addison-Wesley Pub. Co., 1969 | MR | Zbl

[3] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979 | MR | Zbl

[4] Rublev V. S., Elementy teorii grafov. Izomorfizm, planarnost', marshruty v grafakh, YSU, Yaroslavl, 2010 (in Russian)

[5] Umans C., Lenhart W., “Hamiltonian Cycles in Solid Grid Graphs”, Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1997, 496–505 | DOI

[6] Keshavarz-Kohjerdi F., Bagheri A., “An efficient parallel algorithm for the longest path problem in meshes”, The Journal of Supercomputing, 65:2 (2013), 723–741 | DOI