Complexity of correspondence \(H\)-colourings
DOI10.1016/j.dam.2019.11.005zbMath1440.05150arXiv1703.05881OpenAlexW2990687474MaRDI QIDQ2184689
Publication date: 29 May 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.05881
NP-completenesspolynomial algorithmsgraph homomorphismsdichotomy\(H\)-colouringscorrespondence colouringsDP-colourings
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- Computing vertex-surjective homomorphisms to partially reflexive trees
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- List homomorphisms and circular arc graphs
- The complexity of tropical graph homomorphisms
- Correspondence homomorphisms to reflexive graphs
- Graph partitions with prescribed patterns
- 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
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of correspondence \(H\)-colourings
