RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2019, Volume 26, Number 3, Pages 405–419 (Mi mais687)  

Algorithms

NP-completeness and one polynomial subclass of the two-step 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 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.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-07-00823_а
The reported study was funded by RFBR according to the research project № 17-07-00823 A.


DOI: https://doi.org/10.18255/1818-1015-405-419

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, “NP-completeness and one polynomial subclass of the two-step 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 NP-completeness and one polynomial subclass of the two-step graph colouring problem
\jour Model. Anal. Inform. Sist.
\yr 2019
\vol 26
\issue 3
\pages 405--419
\mathnet{http://mi.mathnet.ru/mais687}
\crossref{https://doi.org/10.18255/1818-1015-405-419}


Linking options:
  • http://mi.mathnet.ru/eng/mais687
  • http://mi.mathnet.ru/eng/mais/v26/i3/p405

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020