On the resolution complexity of graph non-isomorphism

DOI10.1007/978-3-642-39071-5_6MaRDI QIDQ5326453zbMATH OpenOpenAlexFDO

Authors Jacobo Torán

Publication date 5 August 2013

Published in Theory and Applications of Satisfiability Testing – SAT 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39071-5_6

Mathematics Subject Classification ID

Complexity of proofs (03F20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• The resolution complexity of random graph \(k\)-colorability
• scientific article; zbMATH DE number 176731
• scientific article; zbMATH DE number 1361471
• Hard examples for resolution
• Graph expansion, Tseitin formulas and resolution proofs for CSP

Cited in

(9)

• Limitations of algebraic approaches to graph isomorphism testing
• A finite-model-theoretic view on propositional proof complexity
• The configurable SAT solver challenge (CSSC)
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Number of variables for graph differentiation and the resolution of GI formulas
• Cutting planes width and the complexity of graph isomorphism refutations
• Resolution with symmetry rule applied to linear equations
• Supercritical size-width tree-like resolution trade-offs for graph isomorphism
• On the generic complexity of the searching graph isomorphism problem

This page was built for publication: On the resolution complexity of graph non-isomorphism

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