×

Semilattice polymorphisms and chordal graphs. (English) Zbl 1284.05125

Summary: 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.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, H.-J., Graphs with edge-preserving majority functions, Discrete Math., 103, 1, 1-5 (1992) · Zbl 0766.05024
[3] Brewster, R.; Feder, T.; Hell, P.; Huang, J.; MacGillivray, G., Near unanimity functions and varieties of reflexive graphs, SIAM J. Discrete. Math., 22, 3, 938-960 (2008) · Zbl 1200.05217
[5] Carvalho, C.; Dalmau, V.; Krokhin, A., Two new homomorphism dualities and lattice operations, J. Logic Comput., 21, 6, 1065-1092 (2011) · Zbl 1231.68121
[6] Dalmau, V.; Pearson, J., Closure functions and width 1 problems, (CP 1999 (1999), Springer-Verlag), 159-173 · Zbl 0957.68081
[7] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, JCTB, 72, 2, 236-250 (1998) · Zbl 0904.05078
[8] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 57-104 (1998) · Zbl 0914.68075
[11] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[12] Hatcher, A., Algebraic Topology (2001), Cambridge University Press
[14] Hell, P.; Rival, I., Retracts in graphs, Canad. J. Math., 39, 544-567 (1987) · Zbl 0627.05039
[16] Jeavons, P.; Cohen, D.; Gyssens C, M., Closure properties of constraints, J. ACM, 44, 4, 527-548 (1997) · Zbl 0890.68064
[17] Larose, B.; Loten, C.; Zádori, L., A polynomial-time algorithm to recognise near-unanimity graphs, J. Algorithms, 55, 2, 177-191 (2005) · Zbl 1101.68960
[18] Larose, B.; Tardif, C., A discrete homotopy theory for binary reflexive structures, Adv. Math., 189, 268-300 (2004) · Zbl 1061.06005
[19] Larose, B.; Zádori, L., Finite posets and topological spaces in locally finite varieties, Algebra Universalis, 52, 2-3, 119-136 (2004) · Zbl 1090.06004
[21] Lin, I.; McKee, T.; West, D., The leafage of a chordal graph, Discuss. Math. Graph Theory, 18, 23-48 (1998) · Zbl 0912.05053
[22] Maróti, M.; Zádori, L., Reflexive digraphs with near unanimity polymorphisms, Discrete Math., 12, 15, 2316-2328 (2012) · Zbl 1245.05059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.