Near-Unanimity Functions and Varieties of Reflexive Graphs

DOI10.1137/S0895480103436748zbMath1200.05217OpenAlexW2045479874MaRDI QIDQ3393427

Richard C. Brewster, Gary MacGillivray, Jing Huang, Pavol Hell, Tomás Feder

Publication date: 20 August 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480103436748

zbMATH Keywords

retractiongraph homomorphismdichotomynear unanimity functionhomomorphism extension

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Bi‐arc graphs and the complexity of list homomorphisms ⋮ Testing list \(H\)-homomorphisms ⋮ The structure of bi-arc trees ⋮ Unnamed Item ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ Semilattice polymorphisms and chordal graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Reflexive graphs with near unanimity but no semilattice polymorphisms ⋮ The complexity of the list homomorphism problem for graphs ⋮ Absolute retracts and varieties generated by chordal graphs ⋮ Building blocks for the variety of absolute retracts ⋮ Unnamed Item ⋮ Graph partitions with prescribed patterns ⋮ Characterizing bipartite graphs which admit a \(k\)-NU polymorphism via absolute retracts

This page was built for publication: Near-Unanimity Functions and Varieties of Reflexive Graphs