List homomorphisms of graphs with bounded degrees

DOI10.1016/j.disc.2005.09.030zbMath1111.05035OpenAlexW1989905036MaRDI QIDQ864125

Tomás Feder, Jing Huang, Pavol Hell

Publication date: 13 February 2007

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.09.030

zbMATH Keywords

polynomial-time algorithmextension problemNP-complete problembi-arc graphedge-asteroidH-colouring problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Unnamed Item ⋮ List homomorphisms of graphs with bounded degrees ⋮ List homomorphisms to reflexive graphs ⋮ Unnamed Item ⋮ Colouring, constraint satisfaction, and complexity ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ List H-coloring a graph by removing few vertices ⋮ Graph partitions with prescribed patterns ⋮ Dichotomy for bounded degree \(H\)-colouring ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Extension problems with degree bounds ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Complexity of homomorphisms to direct products of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List homomorphisms of graphs with bounded degrees
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Algorithmic complexity of list colorings
• Extending graph colorings
• Graph homomorphisms and phase transitions
• The complexity of \(H\)-colouring of bounded degree graphs
• List homomorphisms and circular arc graphs
• On the complexity of the general coloring problem
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Bi‐arc graphs and the complexity of list homomorphisms

This page was built for publication: List homomorphisms of graphs with bounded degrees