The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -