A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Coloring Reconfiguration Problem on Specific Graph Classes O problema de reconfiguração de cores em classes específicas de gráficos

Tatsuhiko HATANAKA, Takehiro ITO, Xiao ZHOU

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Estudamos o problema de transformar um (vértice) c-colorir um gráfico em outro, alterando apenas uma atribuição de cor de vértice por vez, mantendo sempre uma c-coloração, onde c denota o número de cores. Este problema de decisão é conhecido por ser PSPACE-completo mesmo para grafos bipartidos e qualquer constante fixa c ≥ 4. Neste artigo, estudamos o problema do ponto de vista das classes de grafos. Primeiro mostramos que o problema permanece PSPACE-completo para grafos cordais mesmo se c é uma constante fixa. Demonstramos então que, mesmo quando c faz parte da entrada, o problema pode ser resolvido em tempo polinomial para diversas classes de grafos, como k-árvores com qualquer número inteiro k ≥ 1, gráficos divididos e gráficos trivialmente perfeitos.

Publicação
IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.423-429
Data de publicação
2019/03/01
Publicitada
2018/10/30
ISSN online
1745-1361
DOI
10.1587/transinf.2018FCP0005
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Categoria

autores

Tatsuhiko HATANAKA
  Tohoku University
Takehiro ITO
  Tohoku University
Xiao ZHOU
  Tohoku University

Palavra-chave