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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Yoichi HANATANI, Takashi HORIYAMA, Kazuo IWAMA, Suguru TAMAKI, "New Graph Calculi for Planar Non-3-Colorable Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2301-2307, September 2008, doi: 10.1093/ietfec/e91-a.9.2301.
Abstract: The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2301/_p
Copiar
@ARTICLE{e91-a_9_2301,
author={Yoichi HANATANI, Takashi HORIYAMA, Kazuo IWAMA, Suguru TAMAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={New Graph Calculi for Planar Non-3-Colorable Graphs},
year={2008},
volume={E91-A},
number={9},
pages={2301-2307},
abstract={The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2301},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - New Graph Calculi for Planar Non-3-Colorable Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2301
EP - 2307
AU - Yoichi HANATANI
AU - Takashi HORIYAMA
AU - Kazuo IWAMA
AU - Suguru TAMAKI
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2301
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - The Hajos calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.
ER -