Paper Info
Title
Semilattice polymorphisms and chordal graphs
Abstract
We investigate the class of reflexive graphs that admit semilattice polymorphisms, and in doing so, give an algebraic characterisation of chordal graphs. In particular, we show that a graph G is chordal if and only if it has a semilattice polymorphism such that G is a subgraph of the comparability graph of the semilattice. Further, we find a new characterisation of the leafage of a chordal graph in terms of the width of the semilattice polymorphisms it admits. Finally, we introduce obstructions to various types of semilattice polymorphisms, and in doing so, show that the class of reflexive graphs admitting semilattice polymorphisms is not a variety. These are, to our knowledge, the first structural results on graphs with semilattice polymorphisms, beyond the conservative realm.
Year
DOI
Venue
2014
10.1016/j.ejc.2013.10.007
Eur. J. Comb.
Keywords
Field
DocType
structural result,various type,new characterisation,semilattice polymorphism,conservative realm,graph g,reflexive graph,comparability graph,chordal graph,algebraic characterisation
Graph,Discrete mathematics,Combinatorics,Comparability graph,Algebraic number,Chordal graph,If and only if,Semilattice,Mathematics
Journal
Volume
ISSN
Citations 
36,
0195-6698
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Pavol Hell12638288.75
M. Siggers25011.90