For Full-Text 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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Graphs and Networks
Hajos calculus, planar graph, bounded degree graph, coloring, proof system,
Full Text: PDF>>
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.