
Algorithms
NPcompleteness and one polynomial subclass of the twostep graph colouring problem
N. S. Medvedeva^{}, A. V. Smirnov^{} ^{} P.G. Demidov Yaroslavl State University,
Sovetskaya str., 14, Yaroslavl, 150003, Russia
Abstract:
In this paper, we study the twostep 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 NPcompleteness of the problem of twostep colouring. Also we specify some of its properties.
Special interest is paid to the problem of twostep 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 twovertex 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:
twostep graph colouring, NPcompleteness, grid graph, rectangular grid graph.
DOI:
https://doi.org/10.18255/18181015405419
Full text:
PDF file (661 kB)
References:
PDF file
HTML file
UDC:
519.174.7 Received: 14.08.2019 Revised: 11.09.2019 Accepted:13.09.2019
Citation:
N. S. Medvedeva, A. V. Smirnov, “NPcompleteness and one polynomial subclass of the twostep graph colouring problem”, Model. Anal. Inform. Sist., 26:3 (2019), 405–419
Citation in format AMSBIB
\Bibitem{MedSmi19}
\by N.~S.~Medvedeva, A.~V.~Smirnov
\paper NPcompleteness and one polynomial subclass of the twostep graph colouring problem
\jour Model. Anal. Inform. Sist.
\yr 2019
\vol 26
\issue 3
\pages 405419
\mathnet{http://mi.mathnet.ru/mais687}
\crossref{https://doi.org/10.18255/18181015405419}
Linking options:
http://mi.mathnet.ru/eng/mais687 http://mi.mathnet.ru/eng/mais/v26/i3/p405
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  47  Full text:  9  References:  3 
