The complexity of the Hajós calculus for planar graphs

DOI10.1016/j.tcs.2009.12.011zbMath1213.05224OpenAlexW2075186611MaRDI QIDQ2268877

Kazuhisa Seto, Kazuo Iwama, Suguru Tamaki

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/96303

zbMATH Keywords

graph coloringplanar graphproof complexityextended Frege systemsHajós calculus

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Hajós-Type Constructions and Neighborhood Complexes, Grassmann homomorphism and Hajós-type theorems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the tree-like Hajós calculus
• The intractability of resolution
• The edge density of 4-critical planar graphs
• Some simplified NP-complete graph problems
• On the complexity of regular resolution and the Davis-Putnam procedure
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The complexity of the pigeonhole principle
• 4-critical 4-valent planar graphs constructed with crowns.
• Lower bounds for k-DNF resolution on random 3-CNFs
• Applications of a Planar Separator Theorem
• The relative efficiency of propositional proof systems
• Lower bounds for resolution and cutting plane proofs and monotone computations
• The Complexity of the Hajós Calculus
• The Complexity of Propositional Proofs
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• The Complexity of Propositional Proofs
• Linear gaps between degrees for the polynomial calculus modulo distinct primes