The complexity of the Hajos calculus for planar graphs
The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded. (C) 2009 Elsevier B.V. All rights reserved.
hajos calculus planar graph proof complexity graph coloring extended frege systems