Bulletin of the
Korean Mathematical Society BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016
qr-code QR
Code

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2018; 55(1): 81-105

Online first article November 28, 2017      Printed January 31, 2018

https://doi.org/10.4134/BKMS.b160853

Copyright © The Korean Mathematical Society.

Distributive lattice polymorphisms on reflexive graphs

Mark Siggers

Kyungpook National University

Abstract

Go to

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

Article Tools

Stats or Metrics

Share this article on :

Related articles in BKMS