Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy

DOI10.1109/LICS.2015.52MaRDI QIDQ4635829zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau, László Egri, Benoît Larose, Arash Rafiey, Pavol Hell

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2015.52

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Space complexity of list H-colouring: a dichotomy
• The dichotomy of list homomorphisms for digraphs
• The complexity of the list homomorphism problem for graphs
• The complexity of the list homomorphism problem for graphs
• On constraint satisfaction problems below P

Cited in

(12)

• scientific article; zbMATH DE number 7228418 (Why is no real title available?)
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Algebra and the complexity of digraph CSPs: a survey
• The dichotomy of list homomorphisms for digraphs
• Space complexity of list H-colouring: a dichotomy
• Graph isomorphism restricted by lists
• Sparsification lower bounds for list \(H\)-coloring
• Sparsification lower bounds for list H-coloring
• Complexity of the list homomorphism problem in hereditary graph classes
• Symmetric linear arc monadic Datalog and gadget reductions
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs

This page was built for publication: Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy

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