
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Planar Hajós Calculus for Bounded Degree Graphs
Kazuo IWAMA Kazuhisa SETO Suguru TAMAKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E93A
No.6
pp.10001007 Publication Date: 2010/06/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E93.A.1000
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Graphs and Networks Keyword: Hajos calculus, planar graph, bounded degree graph, coloring, proof system,
Full Text: PDF>>
Summary:
The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degreed planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non3colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non3colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.

