Distributive Lattice Polymorphism on Reflexive Graphs
Mark Siggers · arXiv (Cornell University) · 2014
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.