Distributive lattice polymorphisms on reflexive graphs
Bull. Korean Math. Soc. 2018 Vol. 55, No. 1, 81-105
https://doi.org/10.4134/BKMS.b160853
Published online January 31, 2018
Mark Siggers
Kyungpook National University
Abstract : In this paper we give two characterisations of the class of reflexive graphs admitting {\em distributive lattice polymorphisms} and use these characterisations to address the problem of recognition: we find a polynomial time algorithm to decide if a given reflexive graph $G$, in which no two vertices have the same neighbourhood, admits a distributive lattice polymorphism.
Keywords : lattice polymorphism, CSP, distributive lattice, reflexive graph, recognition
MSC numbers : 05C75, 08B05
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd