New Graph Calculi for Planar Non-3-Colorable Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2301-2307
- Publication Date
- 2008/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.9.2301
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
