Distributive lattice polymorphisms on reflexive graphs

MaRDI QIDQ4576639zbMATH OpenFDO

Authors Mark Siggers

Publication date 10 July 2018

Full work available at URL https://arxiv.org/abs/1411.7879

zbMATH Keywords

lattice polymorphism, CSP, distributive lattice, reflexive graph, recognition

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Equational logic, Mal'tsev conditions (08B05)

Abstract: In this paper we give two characterisations of the class of reflexive graphs admitting distributive lattice polymorphisms and use these characterisations to address the problem of recognition: for a reflexive graph G in which no two vertices have the same neighbourhood, we find a polynomial time algorithm to decide if G admits a distributive lattice polymorphism.

Recommendations

• Reflexive graphs with near unanimity but no semilattice polymorphisms
• Reflexive digraphs with near unanimity polymorphisms
• Semilattice polymorphisms and chordal graphs
• Efficient polynomial algorithms for distributive lattices
• A Classification of Reflexive Graphs: The use of “Holes”

Cited in

(8)

• Semilattice polymorphisms and chordal graphs
• scientific article; zbMATH DE number 5492072 (Why is no real title available?)
• Distributive lattices, polyhedra, and generalized flows
• Surjective polymorphisms of directed reflexive cycles
• Reflexive digraphs with near unanimity polymorphisms
• NU polymorphisms on reflexive digraphs
• Reflexive graphs with near unanimity but no semilattice polymorphisms
• Algebra and the complexity of digraph CSPs: a survey

This page was built for publication: Distributive lattice polymorphisms on reflexive graphs

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