Weak near-unanimity functions and digraph homomorphism problems

DOI10.1016/J.TCS.2012.12.025MaRDI QIDQ1945940zbMATH OpenOpenAlexFDO

Authors Gary MacGillivray, Jacobus Swarts

Publication date 17 April 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.12.025

zbMATH Keywords

\(H\)-colouring problemweak near-unanimity functions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Near-Unanimity Functions and Varieties of Reflexive Graphs
• A polynomial-time algorithm for near-unanimity graphs
• Weak total resolvability in graphs
• On the weak-integrity of graphs
• Reflexive digraphs with near unanimity polymorphisms
• Near-Unanimity Polymorphisms on Structures with Finite Duality
• scientific article; zbMATH DE number 4162940
• Posets, near unanimity functions and zigzags
• On weak domination in graphs
• On weak domination in graphs

Cited in

(9)

• Dichotomy for finite tournaments of mixed-type
• Quantified Constraints in Twenty Seventeen
• Menger systems of idempotent cyclic and weak near-unanimity multiplace functions
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• The \(C_{k}\)-extended graft construction
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Reflexive digraphs with near unanimity polymorphisms
• Near-Unanimity Polymorphisms on Structures with Finite Duality
• Complexity and polymorphisms for digraph constraint problems under some basic constructions

This page was built for publication: Weak near-unanimity functions and digraph homomorphism problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945940)