Fixed-point definability and polynomial time on graphs with excluded minors
From MaRDI portal
Publication:5395695
DOI10.1145/2371656.2371662zbMath1281.68129MaRDI QIDQ5395695
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2371656.2371662
05C83: Graph minors
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
68Q19: Descriptive complexity and finite models
Related Items
Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Number of nodal domains of eigenfunctions on non-positively curved surfaces with concave boundary, On symmetric circuits and fixed-point logics, Choiceless Polynomial Time on Structures with Small Abelian Colour Classes, Is Polynomial Time Choiceless?, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs