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

New Graph Calculi for Planar Non-3-Colorable Graphs Novos cálculos gráficos para gráficos planares não coloridos

Yoichi HANATANI, Takashi HORIYAMA, Kazuo IWAMA, Suguru TAMAKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O cálculo de Hajos é um procedimento não determinístico que gera a classe de gráficos não-3 coloríveis. Se todos os gráficos não-3-coloríveis puderem ser construídos em etapas polinomiais pelo cálculo, então NP = co-NP é válido. Até o momento, entretanto, permanece em aberto se existe uma família de gráficos que não pode ser gerada em etapas polinomiais. Para atacar este problema, propomos dois cálculos gráficos PHC e PHC* que geram gráficos planares não tricoloríveis, onde os gráficos intermediários nos cálculos também são restritos a serem planares. Então provamos que PHC e PHC* são sólidos e completos. Também mostramos que PHC* pode simular polinomialmente PHC.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2301-2307
Data de publicação
2008/09/01
Publicitada
ISSN online
1745-1337
DOI
10.1093/ietfec/e91-a.9.2301
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Palavra-chave