The complexity of the Hajós calculus for planar graphs

DOI10.1016/J.TCS.2009.12.011MaRDI QIDQ2268877zbMATH OpenOpenAlexFDO

Authors Kazuo Iwama, Kazuhisa Seto, 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

extended Frege systemsgraph coloringHajós calculusplanar graphproof complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1256654
• The Complexity of the Hajós Calculus
• Exponential lower bounds for the tree-like Hajós calculus
• Space complexity: what makes planar graphs special?
• scientific article; zbMATH DE number 3313427

Cites work

• 4-critical 4-valent planar graphs constructed with crowns.
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• Applications of a Planar Separator Theorem
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Exponential lower bounds for the tree-like Hajós calculus
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1215500 (Why is no real title available?)
• scientific article; zbMATH DE number 1306896 (Why is no real title available?)
• scientific article; zbMATH DE number 1179974 (Why is no real title available?)
• scientific article; zbMATH DE number 2102736 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 5485584 (Why is no real title available?)
• scientific article; zbMATH DE number 3420722 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Lower bounds for k-DNF resolution on random 3-CNFs
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On the complexity of regular resolution and the Davis-Putnam procedure
• Some simplified NP-complete graph problems
• The Complexity of Propositional Proofs
• The Complexity of Propositional Proofs
• The Complexity of the Hajós Calculus
• The complexity of the pigeonhole principle
• The edge density of 4-critical planar graphs
• The intractability of resolution
• The relative efficiency of propositional proof systems

Cited in

(6)

• scientific article; zbMATH DE number 1256654 (Why is no real title available?)
• The Complexity of the Hajós Calculus
• Hajós-type constructions and neighborhood complexes
• Grassmann homomorphism and Hajós-type theorems
• Exponential lower bounds for the tree-like Hajós calculus
• On the planarity of Hanoi graphs

This page was built for publication: The complexity of the Hajós calculus for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268877)