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.E93-A   No.6   pp.1000-1007
Publication Date: 2010/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1000
Print ISSN: 0916-8508
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>>
Buy this Article




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 degree-d 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 non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.