First-order Definable Retraction Problems for Posets and Reflexive Graphs

DOI10.1093/LOGCOM/EXL014MaRDI QIDQ3437257zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau, Andrei Krokhin, Benoît Larose

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

graphsfirst-order definabilityhomomorphismposetsretraction

Mathematics Subject Classification ID

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

Recommendations

• Definability in first-order theories of graph orderings
• Definability in first order theories of graph orderings
• Two consequences of the dichotomy theorem on first order definability of graphs.
• The first order definability of graphs: Upper bounds for quantifier depth
• scientific article; zbMATH DE number 6862042
• The first order definability of graphs with separators via the Ehrenfeucht game
• Dismantling absolute retracts of reflexive graphs
• Absolute Retracts and Varieties of Reflexive Graphs
• scientific article; zbMATH DE number 2086614
• First-order definability on finite structures

Cited in

(6)

• scientific article; zbMATH DE number 6862042 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Majority constraints have bounded pathwidth duality
• CSP duality and trees of bounded pathwidth
• On digraph coloring problems and treewidth duality

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

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