کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653636 | 1632783 | 2014 | 13 صفحه PDF | دانلود رایگان |
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 GG is chordal if and only if it has a semilattice polymorphism such that GG 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.
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 694–706