First-order Definable Retraction Problems for Posets and Reflexive Graphs

DOI10.1093/logcom/exl014zbMath1129.03017OpenAlexW2098354393MaRDI QIDQ3437257

Andrei A. Krokhin, Benoit Larose, Victor Dalmau

Publication date: 14 May 2007

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/6667/1/6667.pdf

zbMATH Keywords

retractionposetsgraphshomomorphismfirst-order definability

Mathematics Subject Classification ID

Partial orders, general (06A06) Classical first-order logic (03B10) Graph theory (05C99) Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Descriptive complexity and finite models (68Q19)

Related Items (5)

On digraph coloring problems and treewidth duality ⋮ Majority constraints have bounded pathwidth duality ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Colouring, constraint satisfaction, and complexity ⋮ CSP duality and trees of bounded pathwidth

This page was built for publication: First-order Definable Retraction Problems for Posets and Reflexive Graphs