Correspondence homomorphisms to reflexive graphs

DOI10.1016/j.endm.2017.10.003zbMath1383.05212OpenAlexW2765119750MaRDI QIDQ2413143

Tomás Feder, Pavol Hell

Publication date: 9 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.003

zbMATH Keywords

NP-completenesshomomorphismdichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Complexity of correspondence \(H\)-colourings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• List homomorphisms and circular arc graphs
• Complexity of conservative constraint satisfaction problems
• Expander graphs and their applications
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Bi‐arc graphs and the complexity of list homomorphisms
• A Proof of the CSP Dichotomy Conjecture

This page was built for publication: Correspondence homomorphisms to reflexive graphs