New Graph Calculi for Planar Non-3-Colorable Graphs
Yoichi Hanatani, Takashi Horiyama, Kazuo Iwama, S. TAMAKI · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2008
The Hajós 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.