The complexity of the Hajós calculus for planar graphs
From MaRDI portal
Publication:2268877
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
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 (2)
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
This page was built for publication: The complexity of the Hajós calculus for planar graphs
